Pagini recente » Cod sursa (job #2500682) | Cod sursa (job #2274453) | Cod sursa (job #961908) | Cod sursa (job #1607401) | Cod sursa (job #2070307)
#include <bits/stdc++.h>
#define lung 2*1000*1000+10
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[lung],b[lung],n,m;
int pi[lung],pos[1024],k;
void citire()
{
f.getline(a,lung-1);
f.getline(b,lung-1);
n=strlen(a);
m=strlen(b);
for(int i=n;i>0;--i)
a[i]=a[i-1];
a[0]=' ';
for(int i=m;i>0;--i)
b[i]=b[i-1];
b[0]=' ';
}
void prefix()
{
int i,q=0;
pi[1]=0;
for(int i=2;i<=n;++i)
{
while(q && a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
int main()
{
int q=0;
citire();
prefix();
//KMP
for(int i=1;i<=m;++i)
{
while(q && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==n)
{
q=pi[n];
++k;
if(k<=1000)
pos[k]=i-n;
}
}
g<<k<<"\n";
for(int i=1;i<=min(k,1000);++i)
g<<pos[i]<<" ";
g<<"\n";
return 0;
}