Pagini recente » Cod sursa (job #1284538) | Cod sursa (job #1786877) | Cod sursa (job #314326) | Cod sursa (job #3162074) | Cod sursa (job #1364515)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000000],d[1000],n,m,nr,i;
char s[2000001],t[2000001];
void Precalculare()
{
int i,k;
pi[0]=0; k=0;
for(i=1;i<m;i++)
{
if(t[i]==t[k]) k++;
else
{
while(k>0&&t[k]!=t[i]) k=pi[k-1];
if(t[k]==t[i]) k++;
}
pi[i]=k;
}
}
void KMP()
{
int i,k=0;
for(i=0;i<n;i++)
{
if(s[i]==t[k]) k++;
else
{
while(k>0&&t[k]!=s[i]) k=pi[k-1];
if(s[i]==t[k]) k++;
}
if(k==m) {nr++; if(nr<=1000) d[nr]=i-m+1; }
}
}
int main()
{
fin>>t;
fin>>s;
n=strlen(s);
m=strlen(t);
Precalculare();
KMP();
fout<<nr<<"\n";
if(nr<=1000) for(i=1;i<=nr;i++) fout<<d[i]<<" ";
else for(i=1;i<=1000;i++) fout<<d[i]<<" ";
return 0;
}