Pagini recente » Borderou de evaluare (job #3198433) | Cod sursa (job #650943) | Borderou de evaluare (job #3275107) | Borderou de evaluare (job #153962) | Cod sursa (job #3333203)
#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 ll NMAX=2e6+5,MOD=1e9+7;
ll dp[NMAX],baza=53,p[NMAX],n,val,valacm,k,temp,i;
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]*p[i])%MOD;
}
dp[0]=b[0]*p[0]%MOD;
for(i=1;i<b.size();i++){
dp[i]=(dp[i-1]+b[i]*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()),1000);
for(i=0;i<k;i++)fout<<afis[i]<<' ';
return 0;
}