1269. Obscene Words Filter
Time limit: 0.5 second
Memory limit: 8 MB
Memory limit: 8 MB
There is a problem to check messages of web-board visitors for the obscene words. Your elder colleagues commit this problem to you. You are to write a program, which check if there is at least one obscene word from the given list in the given text as a substring.
Input
The first line consists of integer n (1 ≤ n ≤ 10000) — an amount of words. The next n lines contain the list of words that we can’t allow to use in our well-educated society. A word may contain any symbol but the ones with codes 0, 10 and 13. The length of each word doesn’t exceed 10000 symbols. The total list of words doesn’t exceed 100 KB. Then there is an integer m — the number of lines of the text. A size of the text doesn’t exceed 900 KB.
Output
the number of line and the number of position separated with a space, where an obscene word occurs for the first time. If there are no obscene words, output “Passed”.
Sample
| input | output |
|---|---|
5 |
6 33 |
Problem Author: Pavel Atnashev
Problem Source: Ural State University championship, October 25, 2003
Problem Source: Ural State University championship, October 25, 2003
Difficulty: 832
题意：问在文章中第一次出现禁忌单词的地方
分析：AC自动机，但这题卡时间卡内存
链表？边目录？No，卡时间
数组？对了一半，卡空间
所以，只能动态的分配孩子的空间
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define INF (1000000001) const int N = ;
struct TreeType
{
char C;
int Next;
int *Child;
unsigned short Len, CLen, Size;
} Tree[N];
//int First[N], To[N], Next[N], Tot;
int n, m, Cnt, Ans = INF;
char Str[N * ];
int Q[N]; /*inline void Insert(int u, int v)
{
Tot++;
To[Tot] = v, Next[Tot] = First[u];
First[u] = Tot;
}*/ inline void Updata(TreeType &T)
{
T.Size += ;
int *p = new int[T.Size + ];
for(int i = ; i < T.CLen; i++) p[i] = T.Child[i];
delete []T.Child;
T.Child = p;
} inline void Ins(char *Str)
{
int Length = strlen(Str + ), x = , Tab;
bool Flag;
For(i, , Length)
{
Flag = ;
/*for(Tab = First[x]; Tab; Tab = Next[Tab])
if(Tree[To[Tab]].C == Str[i])
{
Flag = 1;
x = To[Tab];
break;
}*/
for(Tab = ; Tab < Tree[x].CLen; Tab++)
if(Tree[Tree[x].Child[Tab]].C == Str[i])
{
Flag = , x = Tree[x].Child[Tab];
break;
}
if(!Flag)
{
//Insert(x, ++Cnt);
if(Tree[x].CLen >= Tree[x].Size) Updata(Tree[x]);
Tree[x].Child[Tree[x].CLen++] = ++Cnt;
Tree[Cnt].C = Str[i], x = Cnt;
}
}
Tree[x].Len = Length;
} inline void Input()
{
scanf("%d", &n);
getchar();
For(i, , n)
{
gets(Str + );
Ins(Str);
}
} inline void Build()
{
int Head = , Tail = ;
int u, v, Tab, k, vv;
//for(Tab = First[0]; Tab; Tab = Next[Tab])
for(Tab = ; Tab < Tree[].CLen; Tab++)
Q[++Tail] = Tree[].Child[Tab];
while(Head <= Tail)
{
u = Q[Head++];
//for(Tab = First[u]; Tab; Tab = Next[Tab])
for(Tab = ; Tab < Tree[u].CLen; Tab++)
{
v = Tree[u].Child[Tab];
if(!v) continue;
//for(k = First[Tree[u].Next]; k; k = Next[k])
for(k = ; k < Tree[Tree[u].Next].CLen; k++)
if(Tree[vv = Tree[Tree[u].Next].Child[k]].C == Tree[v].C)
{
Tree[v].Next = vv;
if(Tree[v].Len < Tree[vv].Len)
Tree[v].Len = Tree[vv].Len;
break;
}
Q[++Tail] = v;
}
}
} inline void Solve()
{
//printf("%d\n", Cnt);
Build();
scanf("%d", &m), getchar();
int Length, x, Tab;
bool Flag;
For(Now, , m)
{
gets(Str + );
Length = strlen(Str + ), x = ;
For(i, , Length)
{
do
{
Flag = ;
//for(Tab = First[x]; Tab; Tab = Next[Tab])
for(Tab = ; Tab < Tree[x].CLen; Tab++)
if(Tree[Tree[x].Child[Tab]].C == Str[i])
{
x = Tree[x].Child[Tab], Flag = ;
break;
}
if(!Flag)
{
x = Tree[x].Next;
continue;
}
if(Tree[x].Len)
{
if(Ans > i - Tree[x].Len + ) Ans = i - Tree[x].Len + ;
}
break;
} while(x); }
if(Ans != INF)
{
printf("%d %d\n", Now, Ans);
return;
}
}
printf("Passed\n");
} int main()
{
freopen("F.in", "r", stdin);
freopen("F.out", "w", stdout);
Input();
Solve();
return ;
}