Pagini recente » Cod sursa (job #1746445) | Cod sursa (job #1754484) | Cod sursa (job #600966) | Cod sursa (job #3145718) | Cod sursa (job #2073769)
#include <bits/stdc++.h>
#define LUNG 2*1000*1000+2
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int pi[LUNG],ind[1024],k,n,m;
char a[LUNG],s[LUNG];
void citire()
{
char c;
bool ok=true;
f>>(a+1);
n=strlen(a+1);
f>>(s+1);
m=strlen(s+1);
}
void make_prefix()
{
int j=0;
pi[1]=0;
for(int i=2; i<=n; ++i)
{
while(j&&a[j+1]!=a[i])
j=pi[j];
if(a[j+1]==a[i])
++j;
pi[i]=j;
}
}
void kmp()
{
int j=0;
for(int i=1; i<=m; ++i)
{
while(j&&a[j+1]!=s[i])
j=pi[j];
if(a[j+1]==s[i])
++j;
if(j==n)
{
++k;
if(k<=1000)
ind[k]=i-n;
j=pi[j];
}
}
}
void afisare()
{
g<<k<<"\n";
k=min(k,1000);
for(int i=1; i<=k; ++i)
g<<ind[i]<<" ";
}
int main()
{
citire();
make_prefix();
kmp();
afisare();
return 0;
}