Pagini recente » Borderou de evaluare (job #2603847) | Cod sursa (job #2208754)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001], b[2000001];
int pi[2000001], ans[2000001], s[1001];
int n, m, k, sol;
int main()
{
fin>>a;
fin.get();
fin>>b;
n=strlen(a);
m=strlen(b);
for(int i=n;i>=1;i--)
a[i]=a[i-1];
for(int i=m;i>=1;i--)
b[i]=b[i-1];
a[0]=NULL;
b[0]=NULL;
for(int i=2; i<=n; i++)
{
while(k && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
k=0;
for(int i=2; i<=m; i++)
{
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
ans[i]=k;
if(k==n)
{
sol++;
if(sol<=1000)
s[sol]=i-n;
k=pi[k];
}
}
fout<<sol<<"\n";
if(sol<1000)
for(int i=1; i<=sol; i++)
fout<<s[i]<<" ";
return 0;
}