Pagini recente » Cod sursa (job #2349105) | Cod sursa (job #1304081) | Cod sursa (job #220456) | Cod sursa (job #579607) | Cod sursa (job #2164646)
#include <bits/stdc++.h>
#define N 2000000
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char T[N],P[N];
int L[N],d[N];
int n,m;
int poz[2000000];
void precalc()
{
int i,k=0;
L[0]=0;
for(i=1;i<m;++i)
{
if(P[i]==P[k]) k++;
else
{while(k>0 && P[i]!=P[k]) k=L[k-1];
if(P[i]==P[k]) k++;
}
L[i]=k;
}
}
void kmp()
{
int i,k;
for(i=0;i<n;++i)
{
if(T[i]==P[k]) k++;
else
{while(k>0 && T[i]!=P[k]) k=L[k-1];
if(T[i]==P[k]) k++;
}
d[i]=k;
}
}
int main()
{
fin>>P>>T;
n=strlen(T);
m=strlen(P);
precalc();
int i;
int ct=0;
kmp();
for(i=0;i<n;++i)
if(d[i]==m)
{
ct++;
poz[ct]=i-m+1;
}
fout<<ct<<"\n";
for(i=1;i<=ct;++i) fout<<poz[i]<<" ";
return 0;
}