Pagini recente » Cod sursa (job #554115) | Borderou de evaluare (job #560578) | Borderou de evaluare (job #3278504) | Cod sursa (job #93049) | Cod sursa (job #3333201)
#include <iostream>
#include<fstream>
#define ll long long
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");const int NMAX=2e6+5;
ll dp[NMAX],baza=60,p[NMAX],n,val,valacm,k,temp,i;const int MOD=1e9+7;
vector<int>afis;
string a,b;
int main()
{
fin>>a>>b;
k=a.size();
n=max(a.size(),b.size());
p[0]=1;
for(i=1;i<=n;i++)p[i]=p[i-1]*baza%MOD;
for(i=0;i<a.size();i++){
val=(val+(a[i]-'A'+1)*p[i])%MOD;
}
dp[0]=(b[0]-'a'+1)*p[0]%MOD;
for(i=1;i<b.size();i++){
dp[i]=(dp[i-1]+(b[i]-'A'+1)*p[i])%MOD;
}
for(i=a.size()-1;i<b.size();i++){
if(i==a.size()-1)valacm=dp[i];
else valacm=(dp[i]-dp[i-k]+MOD)%MOD;
temp=(val*p[i-(a.size()-1)])%MOD;
if(temp==valacm)afis.push_back(i-k+1);
}
fout<<afis.size()<<'\n';
k=min(int(afis.size()),999);
for(i=0;i<k;i++)fout<<afis[i]<<' ';
return 0;
}