Pagini recente » Cod sursa (job #156306) | Cod sursa (job #1550405) | Cod sursa (job #2836387) | Cod sursa (job #125975) | Cod sursa (job #2073770)
#include <bits/stdc++.h>
#define LUNG 2*1000*1000+2
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
//FILE *f=fopen("strmatch.in","r");
int pi[LUNG],ind[1024],k,n,m;
char a[LUNG],s[LUNG];
void citire()
{
char c;
bool ok=true;
/* while(fscanf(f,"%c",&c)&&c!='\n')
{
a[++n]=c;
if(a[n]!='A')
ok=0;
}
if(ok==1)
{
g<<"1\n0\n";
exit(0);
}
while(fscanf(f,"%c",&c)&&c!='\n')
{
s[++m]=c;
}
*/
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;
}