Pagini recente » Cod sursa (job #137868) | Cod sursa (job #763717) | Cod sursa (job #2290983) | Cod sursa (job #713413) | Cod sursa (job #611033)
Cod sursa(job #611033)
#include<cstdio>
#include<vector>
#include<cstring>
#include<ctype.h>
#define Nmax 2000010
using namespace std;
char a[Nmax],b[Nmax];
int N,M,p[Nmax],nr;
vector <int> pot;
void prefix(){
int k=-1;
p[0]=-1;
for(int i=1;i<N;++i){
// cautam ultimul prefix gasit anterior, pentru care
//urmatoarea litera dupa el este identica cu a[i]
while(k>-1 && a[k+1] != a[i])
k=p[k];
// daca literele sunt egale inseamna ca exista
//un prefix egal cu sufixul de aceeasi lungime (k+1)
if(a[k+1] == a[i])
k++;
// pentru fiecare pozitie de la 1 la N retinem lungimea
//celui mai lung prefix egal cu sufixul
p[i]=k;
}
}
void kmp(){
int q=-1;
for(int i=0;i<M;++i){
// ca la prefix, cautam ultima stare valabila dupa
//concatenarea ultimei liter
while(q>-1 && a[q+1]!=b[i])
q=p[q];
// daca literele se potrivesc adaugam litera la
//starea actuala
if(a[q+1]==b[i])
q++;
// daca am gasit un sir de lungime N ce
//verifica automatul -> am gasit o potrivire
if(q+1==N)
if(++nr <=1000)
pot.push_back(i-N+1);
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,Nmax,stdin);
fgets(b,Nmax,stdin);
if(!isalpha(a[strlen(a)-1]))
a[strlen(a)-1]='\0';
N=strlen(a);
if(!isalpha(b[strlen(b)-1]))
b[strlen(b)-1]='\0';
M=strlen(b);
prefix();
kmp();
printf("%d\n",nr);
for(vector<int>::iterator it=pot.begin();it!=pot.end();++it)
printf("%d ",*it);
return 0;
}