Есенен турнир - Шумен 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;
}
Автор: Валентин Михов
обратно към текущ брой
|