Pagini recente » Cod sursa (job #1687319) | Cod sursa (job #1245574) | Monitorul de evaluare | Cod sursa (job #1124008) | Cod sursa (job #169867)
Cod sursa(job #169867)
#include<stdio.h>
#include<string.h>
#define N 2000007
int p[N], m, n, sol[1005], nr;
char a[N], b[N];
void init_p(){//stabileste pentru fiecare pref, [q], care e lung celui mai mare pref [k],care e suf pt el (k<q)
int k=0,q;
m=strlen(a+1);
n=strlen(b+1);
p[1]=0;
for(q=2; q<=m; ++q){
while(k && a[k+1]!=a[q])//incerc toate sufixele lui [q-1] (incerc sa adaug un caracter)
k=p[k];//parcurg pref care sunt suf ale lui [q-1]
if(a[k+1]==a[q])//daca am gasit sufix
++k;//acest sufix are lungimea mai mare cu 1 decat sufixul lui [q-1] la care-l adaug
p[q]=k;
}
}
void kmp(){
int i,q=0;
for(i=1; i<=n ;++i){
while(q && a[q+1]!=b[i])//incerc toate pref care au ultimul car=b[i-1] (suf ale celui de la pasul i-1)
q=p[q];//parcurg pref care au ultimul car b[i-1] (pref ale celui pe care l-am ales inainte)
if(a[q+1]==b[i])//daca am gasit un pref [q] cu ult car b[i-1] si care are a[q+1]=b[i],
++q;//atunci [q+1] este pref cel mai mare al lui a care are ult car=b[i]
if(q==m){
if(nr<1000)
sol[nr++]=i-m;
else
++nr;
}
}
}
void citire(){
scanf("%s\n%s",a+1,b+1);
}
void scrie(){
printf("%d\n",nr);
int min = (nr < 1000 ? nr : 1000);
for(int i=0; i<min-1; ++i)
printf("%d ",sol[i]);
printf("%d\n",sol[min-1]);
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
init_p();
kmp();
scrie();
return 0;
}