Pagini recente » Cod sursa (job #2183058) | Cod sursa (job #2334654) | Cod sursa (job #1312117) | Cod sursa (job #2367239) | Cod sursa (job #2387494)
#include <fstream>
#include <string.h>
#define nMax 2000001
#define mMax 2000001
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Urm[mMax];
char T[nMax],P[mMax];
int n,m;
void KMP(char *P)
{
int k=-1,x;
Urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0 && P[k+1]!=P[x]) k=Urm[k];
if(P[k+1]==P[x]) k++;
Urm[x]=k;
}
}
int main()
{
int i,x=-1;
fin.getline(P,2000000);
fin.getline(T,2000000);
n=strlen(T); m=strlen(P);
KMP(P);
int ct=0;
int v[200000];
for(i=0;i<n;i++)
{
while(x>0 && P[x+1]!=T[i]) x=Urm[x];
if(P[x+1]==T[i]) x++;
if(x==m-1)
{
v[++ct]=i-m+1;
x=Urm[x];
}
}
fout<<ct<<'\n';
for(int i=1;i<=min(ct,1000);i++) fout<<v[i]<<' ';
return 0;
}