Pagini recente » Cod sursa (job #598946) | Cod sursa (job #212979) | Cod sursa (job #1999869) | Cod sursa (job #1544263) | Cod sursa (job #2359097)
#include <bits/stdc++.h>
/// KMP
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int NMAX=2e6+5;
int LPS[NMAX],apar[NMAX],N,M;
char txt[NMAX],pat[NMAX];
void LPSCompute()
{
LPS[0]=0;
int i=1,j=0;
while(i<M)
{
if(pat[i]==pat[j])
{
LPS[i]=j+1;
j++;
i++;
}
else
{
if(j==0) LPS[i++]=0;
else j=LPS[j-1];
}
}
}
void KMP()
{
int i=0,j=0,num=0;
while(i<N)
{
if(pat[j]==txt[i])
{
i++;
j++;
}
if(j==M)
{
apar[++num]=i-j;
j=LPS[j-1];
}
else if(pat[j]!=txt[i] && i<N)
{
if(j!=0) j=LPS[j-1];
else i++;
}
}
fout<<num<<'\n';
for(int k=1;k<=min(num,1000);k++) fout<<apar[k]<<" ";
}
int main()
{
fin>>pat>>txt;
M=strlen(pat);
N=strlen(txt);
LPSCompute();
KMP();
return 0;
}