Pagini recente » Cod sursa (job #707156) | Cod sursa (job #2480794) | Cod sursa (job #301453) | Cod sursa (job #824496) | Cod sursa (job #1690338)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream qu("strmatch.in");
ofstream w("strmatch.out");
char s[2000010],d[2000010];
int n,m,k,pi[2000010],poz[1020];
void prefix()
{
int i;
for(i=2;i<=n;i++)
{
while(k>0 && ( s[k+1] != s[i] ))
k=pi[k];
if(s[k+1]==s[i])
++k;
pi[i]=k;
}
}
int main()
{int i,j,q=0;;
qu.getline(s,2000000);
qu.getline(d,2000000);
n=strlen(s);
m=strlen(d);
for(i=n;i>=1;i--) s[i]=s[i-1];
for(i=m;i>=1;i--) d[i]=d[i-1];
s[0]=' ';
d[0]=' ';
prefix();
k=0;
for(i=1;i<=m;i++)
{
while(q && s[q+1]!=d[i])
q=pi[q];
if(s[q+1]==d[i])
++q;
if(q==n)
{
q=pi[n];
++k;
if(k<=1000)
poz[k]=i-n;
}
}
int x;
if(k<1000) x=k;
else x=1000;
w<<k<<"\n";
for(i=1;i<=x;i++) w<<poz[i]<<" ";
return 0;
}