Pagini recente » Cod sursa (job #1032315) | Cod sursa (job #1191716) | Cod sursa (job #1407084) | Cod sursa (job #3286586) | Cod sursa (job #2986028)
#include <bits/stdc++.h>
#define L long long
#define Lq set<int>::iterator
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
/*int n,i,j;
char ch,v[1000001];
int main()
{
cin>>n;
for(i=0; i<n; ++i)
{
cin>>ch,v[i]=ch;
st1+=ch;
p[st1]=1;
for(j=1; j<=i-2; --j)
{
if(j==1)
{
str2a=ch;
}
else
{
string str2a;
str2a.clear();
str2a+=v[i-j+1];
str2a+=str2;
}
cout<<str2a<<" ";
strcpy(str2,str2a);
}
cout<<"\n";
}
}*/
string a,b;
int pi[2000001],nr,v[1001];
int main()
{
in>>a>>b;
int n=a.size(),k=-1;
pi[0]=0;
for(int i=1; i<n; ++i)
{
while(k>-1 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
++k;
pi[i]=k;
}
int m=b.size(),q=-1;
for(int i=0; i<m; ++i)
{
while(q>-1 && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==n-1)
{
++nr;
if(nr<=1000)
v[nr]=i-n+1;
}
}
out<<nr<<"\n";
for(int i=1; i<=nr; ++i)
out<<v[i]<<" ";
}