Pagini recente » Cod sursa (job #580744) | Cod sursa (job #2218570) | Cod sursa (job #2713670) | Cod sursa (job #1697095) | Cod sursa (job #1524124)
#include <fstream>
#include <cstring>
#define MAX 2000010
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
int U[MAX+5], n, m, sol[MAX+5], nr;
char T[MAX+5], P[MAX+5];
void Prel(char *P)
{
int x, k=-1;
U[0]=0;
for(x=1; x<m; x++)
{
while(k>0 and P[k+1]!=P[x]) k=U[k];
if(P[k+1]==P[x]) k++;
U[x]=k;
}
}
void KMP()
{
int i, k=-1;
for(i=0; i<n; i++)
{
while(k>0 and P[k+1]!=T[i]) k=U[k];
if(P[k+1]==T[i])k++;
if(k==m-1)
{
sol[++nr]=i-m+1;
k=U[k];
}
}
}
int main()
{
f.getline(P, MAX+3);
f.getline(T, MAX+3);
n=strlen(T);
m=strlen(P);
Prel(P);
KMP();
g<<nr<<'\n';
for(int i=1; i<=min(nr,1000); i++) g<<sol[i]<<' ';
}