Текущ брой на Списание ИнфоМан
 


Есенен турнир - Шумен 2005, Задача C1.Хипервръзка

Уловието на задачата може да прочетете тук.

Решение

Важното в тази задача е да се прочетат и да се осмислят добре условията за това кога един низ е връзка. Едно от ключовите условия е номер 5, от което следва, че не е възможно да има подвръзка на някоя връзка, т.е. достатъчно е да се намерят всички райони от текста съставени от букви, цифри, наклонени черти и точки и да се провери дали покриват всички критерии за връзка. Това може да стане линейно по дължината на текста. Алгоритъмът е следният:

1.       Започва се сканиране на текста от началото.

2.       Сканира се докато се намери буква или цифра, което е начало на потенциален низ.

3.       Сканира се нататък докато не се стигне до знак различен от буква, цифра, наклонена черта или точка.

4.       Проверява се така намереният низ дали е връзка, като се види дали няма две последователни точки и дали има точка след последната наклонена черта и буквите след това дали са 2,3 или 4.

5.       Ако низа е връзка, проверява се дали преди него има низа http://. Тук има един важен момент, тъй като низа http:// ще е вече отпечатан, ако се записва изхода направо на стандартния изход. Едно възможно решение на проблема е да се записва изхода в един буфер и ако трябва да се вземе http:// просто трябва да се изтрият няколко знака от края на буфера. Друго възможно решение е да се гледа на всяка стъпка дали няма http:// и да се проверяваме дали след този низ има връзка.

6.       Всеки знак, който не е буква, цифра, наклонена черта или точка просто се отпечатва.

7.       Повтаря се стъпка 2 докато не свърши текста.

Примерна реализация


#include <stdio.h>
#include <string.h>

#define MAXN 15000

char line[MAXN];
char out[10 * MAXN];
char tmp[MAXN];

int goodC(char ch)
{
    if (ch >= 'a' && ch <= 'z') return 1;
    if (ch >= 'A' && ch <= 'Z') return 1;
    if (ch >= '0' && ch <= '9') return 1;
    if (ch == '/') return 1;
    if (ch == '.') return 1;

    return 0;
}

int validLink(int st, int en)
{
    int i;
    // Check for .
    int found = 0;
    for (i = st;i <= en;i++)
        if (line[i] == '.')
        {
            found = 1;
            if (i != en && line[i + 1] == '.') return 0;
        }

    if (!found) return 0;

    // Find last .
    for (i = en;line[i] != '.' && line[i] != '/';i--);
    
    if (line[i] == '.' && (en - i <= 1 || en - i >= 5)) return 0;

    return 1;
}

int main()
{
    // Read line by line
    while (fgets(line, MAXN, stdin))
    {
        int len = strlen(line);
        int curr = 0;

        while (curr < len)
        {
            if ((line[curr] >= 'a' && line[curr] <= 'z') || 
                (line[curr] >= 'A' && line[curr] <= 'Z') || 
                (line[curr] >= '0' && line[curr] <= '9'))
            {
                int end = curr + 1;
                // Begging of possible href
                while (end < len && goodC(line[end])) end++;

                end--;

                if (validLink(curr, end))
                {
                    // Check for http://
                    if (curr >= 7 && 
                        strncmp(&line[curr] - 7, "http://", 7) == 0)
                    {
                        curr -= 7;
                        out[strlen(out) - 7] = 0;
                    }

                    strncpy(tmp, &line[curr], end - curr + 1);
                    tmp[end - curr + 1] = 0;

                    sprintf(&out[strlen(out)], 
                            "<a href=\"%s\">%s</a>", tmp, tmp);

                    curr = end + 1;
                }
                else
                {
                    strncpy(tmp, &line[curr], end - curr + 1);
                    tmp[end - curr + 1] = 0;
                    sprintf(&out[strlen(out)], "%s", tmp);
                    curr = end + 1;
                }
            }
            else
            {
                sprintf(&out[strlen(out)], "%c", line[curr]);
                curr++;
            }
        }
    }
    printf("%s", out);
    return 0;
}


Автор: Валентин Михов


обратно към текущ брой