Pagini recente » Cod sursa (job #1324348) | Cod sursa (job #2487102) | Cod sursa (job #3183262) | Cod sursa (job #1021773) | Cod sursa (job #303559)
Cod sursa(job #303559)
#include<cstring>
#include<cstdio>
#include<vector>
#define CH (*s-'0')
using namespace std;
struct trie{
int c;
int nrfii;
int ord;
trie *fiu[100];
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[2050000];
char bed[2005000];
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,state,st,nrc=0,last=0,length;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(mead,2050000,stdin);
fgets(bed,205000,stdin);
ins(A,mead,0);
int len=strlen(mead)-1;
length=strlen(bed)-1;
F.push_back(V[0]);
F.push_back(V[0]);
for(i=2;i<=len;i++){
state=F[i-1]->ord;
last=gf(state,mead+i-1);
F.push_back(V[last]);
}
state=0;
int gasit=0;
for(i=0;i<length;i++){
if(state==len){
state=F[len]->ord;
}
state=gf(state,bed+i);
if(state==0) {
if(gasit==1){
i--;
state=0;
gasit=2;
}
if(gasit==2){
i++;
state=0;
gasit=0;
}
state=F[state]->ord;
}else{
gasit=1;
}
if(state==len){
L.push_back(i-len);
nrc++;
}
}
printf("%d\n",nrc);
for(int i=0;i<L.size();i++){
printf("%d ",L[i]+1);
}
return 0;
}