Oulipo
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6227 Accepted Submission(s):
2513
a book, La disparition, without the letter 'e'. He was a member of the Oulipo
group. A quote from the book:
Tout avait Pair normal, mais tout
s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain,
l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait
au roman : stir son tapis, assaillant à tout instant son imagination,
l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un
non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la
raison : tout avait l’air normal mais…
Perec would probably have scored
high (or rather, low) in the following contest. People are asked to write a
perhaps even meaningful text on some subject with as few occurrences of a given
“word” as possible. Our task is to provide the jury with a program that counts
these occurrences, in order to obtain a ranking of the competitors. These
competitors often write very long texts with nonsense meaning; a sequence of
500,000 consecutive 'T's is not unusual. And they never use spaces.
So we
want to quickly find out how often a word, i.e., a given string, occurs in a
text. More formally: given the alphabet {'A', 'B', 'C', …, 'Z'} and two finite
strings over that alphabet, a word W and a text T, count the number of
occurrences of W in T. All the consecutive characters of W must exactly match
consecutive characters of T. Occurrences may overlap.
number: the number of test cases to follow. Each test case has the following
format:
One line with the word W, a string over {'A', 'B', 'C', …, 'Z'},
with 1 ≤ |W| ≤ 10,000 (here |W| denotes the length of the string W).
One line
with the text T, a string over {'A', 'B', 'C', …, 'Z'}, with |W| ≤ |T| ≤
1,000,000.
should contain a single number, on a single line: the number of occurrences of
the word W in the text T.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue> using namespace std;
const int maxn=; struct node{ node *child[maxn];
node * fail ; //失败指针
int tail ; };
void init(node * tmp){
for(int i=;i<maxn;i++)
tmp->child[i]=NULL;
tmp->fail=NULL;
tmp->tail=;
} //建立一颗字典树 void Buildtree(const char ss [] ,node * root){
node *cur;
for(int i=; ss[i] ; i++){
int no =ss[i]-'A';
if(root->child[no]==NULL){
cur = new node ;
init(cur);
root->child[no]=cur;
}
root = root->child[no];
}
root->tail++;
} //构造失败指针
void BuildFail(node * root){ queue<node *> tmp;
tmp.push(root);
node *cur,*po;
while(!tmp.empty()){
cur = tmp.front();
tmp.pop(); //出队列
for(int i= ; i<maxn ; i++){
if( cur->child[i] != NULL ){
if(cur==root){
cur->child[i]->fail=root; //指向树根
}else{
po = cur ;
while(po->fail){
if(po->fail->child[i]){
cur->child[i]->fail=po->fail->child[i];
break;
}
po = po->fail;
}
if(po->fail==NULL)
cur->child[i]->fail=root;
}
tmp.push(cur->child[i]);
}
}
}
} //查询
int Query(char ss [] , node *root){ node *cur , *tmp;
cur =root;
int pos=-,res=; for(int i=; ss[i] ;i++){ pos= ss[i]-'A';
while(cur->child[pos]==NULL&&cur!=root)
cur = cur->fail;
cur = cur->child[pos];
if(cur==NULL) cur=root;
tmp = cur;
while(tmp!=root&&tmp->tail>){
res+=tmp->tail;
tmp = tmp->fail;
}
} return res; }
char sa[],sb[];
int main(){
int te;
node *root;
scanf("%d",&te);
while(te--){
root = new node ;
init(root);
scanf("%s %s",sa,sb);
Buildtree(sa,root);
BuildFail(root);
int ans =Query(sb,root);
printf("%d\n",ans);
}
return ;
}