Pagini recente » Cod sursa (job #3232967) | Cod sursa (job #238236) | Cod sursa (job #1203305) | Cod sursa (job #3121654) | Cod sursa (job #194309)
Cod sursa(job #194309)
#include <fstream>
using namespace std;
const int TMAX=2000002,PMAX=1001;
char T[TMAX],P[TMAX];
int n,m,pi[TMAX],poz[PMAX],nr;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void prefix(){
int i,x=0;
pi[0]=0;
for (i=1;i<m;++i){
while (x>0 && P[x]!=P[i]) x=pi[x-1];
if (P[x]==P[i]) x++;
pi[i]=x;
}
}
void kmp(){
int i,x=0;
for (i=0;i<n;++i){
while (x>0 && P[x]!=T[i]) x=pi[x-1];
if (P[x]==T[i]) x++;
if (x==m) { ++nr;
if (nr<=1000) poz[nr]=i-m+1;
x=pi[x-1];}
}
g<<nr<<'\n';
if (nr>1000) nr=1000;
for (i=1;i<=nr;++i) g<<poz[i]<<' ';
}
int main(){
f.getline(P,TMAX);
m=strlen(P);
f.getline(T,TMAX);
n=strlen(T);
prefix();
kmp();
return 0;
}