Pagini recente » Cod sursa (job #1612222) | Cod sursa (job #1464886) | Cod sursa (job #1445207) | Cod sursa (job #3226805) | Cod sursa (job #2870782)
#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<=m;i++) put[i]=1LL*put[i-1]*baza%mod;
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;
}
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 <<" ";
}