Pagini recente » Cod sursa (job #826730) | Cod sursa (job #2154133) | Cod sursa (job #983707) | Cod sursa (job #424340) | Cod sursa (job #1207417)
//KMP
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
char pattern[NMAX],text[NMAX];
int pi[NMAX],overlap[NMAX];
int sol[NMAX];
int main()
{
int i,len,dr,length;
fin>>(pattern+1);
fin>>(text+1);
length=strlen(pattern+1);
pi[1]=0;
for (i=2;i<=length;i++)
if (pattern[i]==pattern[pi[i-1]+1])
pi[i]=pi[i-1]+1;
else
{
dr=pi[i-1];
while (dr && pattern[dr+1]!=pattern[i]) dr=pi[dr];
if (pattern[dr+1]==pattern[i]) pi[i]=dr+1;
}
len=strlen(text+1);
for (i=1;i<=len;i++)
{
if (text[i]==pattern[overlap[i-1]+1])
overlap[i]=overlap[i-1]+1;
else
{
dr=overlap[i-1];
while (dr && pattern[dr+1]!=text[i]) dr=pi[dr];
if (pattern[dr+1]==text[i]) overlap[i]=dr+1;
}
if (overlap[i]==length) sol[++sol[0]]=i-length;
}
fout<<sol[0]<<"\n";
for (i=1;i<=min(sol[0],1000);i++) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}