[C++] 純文本查看 復制代碼
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct Trie
{
int contain;
int number;
Trie* next[26];
Trie* fail;
Trie* pre;
Trie(){
for(int i = 0 ; i < 26 ; i++)
next = NULL;
};
Trie(int n , Trie *p){
number = n;
contain = -1;
for(int i = 0 ; i < 26 ; i++)
next = NULL;
pre = p;
fail = pre;
};
};
bool yes[1024];
Trie* root;
int n;
char str[1000010];
//convert
int cv(int a)
{
return a-'a';
}
void Insert(char word[], int num)
{
Trie* p = root;
for(int i = 0 ; word ; i++)
{
Trie *& nxt = p->next[cv(word)];
if(nxt == NULL) // !!!
{
nxt = new Trie(cv(word), p);
}
p = nxt;
}
p->contain = num;
}
inline void Build_Fail()
{
queue<Trie*> que;
Trie* p = root;
for(int i = 0 ; i < 26 ; i++)
if(p->next != NULL)
for(int j = 0 ; j < 26 ; j++)
if(p->next->next[j] != NULL)
que.push(p->next->next[j]);
while(que.size())
{
p = que.front(); que.pop();
while(p->fail != root)
{
p->fail = p->fail->fail;
if(p->fail->next[p->number] != NULL)
break;
}
for(int i = 0 ; i < 26 ; i++)
if(p->next != 0)
que.push(p->next);
}
}
inline void AC()
{
}
int main()
{
int t;
char word[64];
scanf("%d", &t);
while(t--)
{
scanf("%s", str);
scanf("%d", &n);
for(int i = 0 ; i < n ; i++)
{
scanf("%s", word);
for(int j = 0 ; word[j] ; j++)
if('A' <= word[j] && word[j] <= 'Z')
word[j] = word[j] + 'a'-'A';
Insert(word, i);
}
Build_Fail();
AC();
}
}