Pagini recente » Cod sursa (job #2830924) | Cod sursa (job #2820258) | Cod sursa (job #2799589) | Cod sursa (job #2799151) | Cod sursa (job #3293064)
#include <bits/stdc++.h>
using namespace std;
unsigned long long mod=1e9+7,b=31,p[2000005];
string s1,s2;
vector <int> v;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
p[0]=1;
for(int i=1;i<=2000000;++i)
{
p[i]=(p[i-1]*b)%mod;
}
cin>>s1>>s2;
unsigned long long n1=0,n2=0;
for(int i=0;i<s1.size();++i)
{
n1=(n1*b+s1[i])%mod;
}
for(int i=0;i<s1.size();++i)
{
n2=(n2*b+s2[i])%mod;
}
if(n2==n1)
{
v.push_back(0);
}
for(int i=1;(i+s1.size()-1)<s2.size();++i)
{
int j=i+s1.size()-1;
n2=(mod+n2-(1LL*s2[i-1]*p[s1.size()-1])%mod)%mod;
n2=((1LL*n2*b)%mod+s2[j])%mod;
if(n1==n2)
{
v.push_back(i);
}
}
cout<<v.size()<<"\n";
for(int i=0;i<v.size();++i)
{
cout<<v[i]<<" ";
}
return 0;
}