Pagini recente » Cod sursa (job #1744818) | Cod sursa (job #2454936) | Cod sursa (job #706868) | Cod sursa (job #1471199) | Cod sursa (job #2304891)
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#define MAXN 2000000
using namespace std;
string a, b;
int z[MAXN+5];
vector<int> ans;
inline int maxim( int a, int b )
{
if( a<b )
a=b;
return a;
}
int main()
{
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
cin>>a>>b;
int n=a.size();
a=a+' '+b;
int m=a.size();
int st=0, dr=0;
z[0]=1;
for( int i=1;i<m;i++ )
{
z[i]=z[i-st];
if( i+z[i]>=dr )
{
z[i]=maxim(0,dr-i);
st=i;
dr=i+z[i];
}
while( i+z[i]<m && a[z[i]]==a[i+z[i]] )
{
z[i]++;
dr++;
}
if( z[i]==n )
ans.push_back(i-n-1);
}
cout<<ans.size()<<'\n';
for( vector<int>::iterator it=ans.begin();it!=ans.end();it++ )
cout<<*it<<' ';
return 0;
}