Pagini recente » Cod sursa (job #1620695) | Cod sursa (job #458245) | Cod sursa (job #2313315) | Cod sursa (job #142403) | Cod sursa (job #303023)
Cod sursa(job #303023)
#include<cstring>
#include<cstdio>
#include<vector>
#define CH (*s-'A')
using namespace std;
struct trie{
int c;
int nrfii;
int ord;
trie *fiu[58];
trie(){
c=0;
ord=0;
nrfii=0;
memset(fiu,0,sizeof(fiu));
}
};
trie *A=new trie;
vector<trie *> V;
vector<trie *> F;
vector<int> L;
char mead[2000000];
char bed[2000000];
int gf(int state,char *s){
if(V[state]->fiu[CH]!=0) return V[state]->fiu[CH]->ord;
else return 0;
}
void ins(trie *tr,char *s,int k){
if(*s=='\n'){
tr->c++;
tr->ord=k;
V.push_back(tr);
return ;
}
if(tr->fiu[CH]==0){
tr->fiu[CH]=new trie;
tr->nrfii++;
if(tr->ord==0) tr->ord=k;
V.push_back(tr);
}
ins(tr->fiu[CH],s+1,k+1);
}
int main(){
int i;
int state;
int st;
int nrc=0;
int last=0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(mead,35,stdin);
ins(A,mead,0);
int len=strlen(mead)-1;
F.push_back(V[0]);
F.push_back(V[0]);
for(i=2;i<=len;i++){
state=F[i-1]->ord;
F.push_back(V[gf(state,mead+i-1)]);
}
fgets(bed,35,stdin);
int length=strlen(bed)-1;
state=0;
for(i=0;i<length;i++){
st=gf(state,bed+i);
if(st==0) {
if(state==len) {
L.push_back(last);
last=i-(F[state]->ord);
state=F[state]->ord+1;
nrc++;
}
else state=F[state]->ord;
}else state=st;
if(state==1) last=i;
}
printf("%d\n",nrc);
for(i=0;i<L.size();i++){
printf("%d ",L[i]);
}
return 0;
}