Pagini recente » Cod sursa (job #882770) | Cod sursa (job #1148476) | Cod sursa (job #2797143) | Cod sursa (job #18168) | Cod sursa (job #2870788)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int mod=1e9,baza=31;
char s[2000005],s1[2000005];
int hashs[2000005],hashs1[2000005];
int put[2000005];
int sub1(int i,int j)
{
return (hashs1[j]-(1LL*hashs1[i-1]*put[j-i+1]%mod)+mod)%mod;
}
vector <int> ans;
int main()
{
fin >>(s+1)>>(s1+1);
int n=strlen(s+1);
int m=strlen(s1+1);
put[0]=1;
for (int i=1; i<=n; i++)
{
hashs[i]=(1LL*hashs[i-1]*baza+s[i]-'A'+1)%mod;
}
for (int i=1; i<=m; i++)
{
hashs1[i]=(1LL*hashs1[i-1]*baza+s1[i]-'A'+1)%mod;
put[i]=1LL*put[i-1]*baza%mod;
}
for (int i=1; i<=m-n+1; i++)
{
int sb1=sub1(i,i+n-1);
if (sb1==hashs[n])
{
ans.push_back(i);
}
}
fout << ans.size() <<"\n";
for (int i=0; i<ans.size(); i++) fout << ans[i]-1 <<" ";
}