趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 jd3 於 2014-9-17 23:29 編輯
我真的不知道為什麼只要動到nxt就會RE啊啊啊啊啊連判斷式都死掉...
RE的地方 : " if(nxt == NULL) "
(旁邊有驚嘆號的地方)
[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[i] = NULL;
};
Trie(int n , Trie *p){
number = n;
contain = -1;
for(int i = 0 ; i < 26 ; i++)
next[i] = 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] ; i++)
{
Trie *& nxt = p->next[cv(word[i])];
if(nxt == NULL) // !!!
{
nxt = new Trie(cv(word[i]), 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[i] != NULL)
for(int j = 0 ; j < 26 ; j++)
if(p->next[i]->next[j] != NULL)
que.push(p->next[i]->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[i] != 0)
que.push(p->next[i]);
}
}
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();
}
}
|