Pagini recente » Cod sursa (job #2057582) | Cod sursa (job #300547) | Cod sursa (job #669430) | Cod sursa (job #3178420) | Cod sursa (job #2417713)
#include <bits/stdc++.h>
#define nmax 2000005
#define MOD 1000000007
#define lld long long
using namespace std;
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
char a[nmax], b[nmax];
int ln;
vector<int>ans;
lld expH, currH, pw[nmax];
const lld pww = 31;
int main()
{
fscanf(fin,"%s\n",a);
fscanf(fin,"%s\n",b);
pw[0] = 1;
ln = 1;
for (int i=1;a[i];++i)
pw[i] = (pw[i-1] * pww) % MOD, ++ln;
if (!b[ln-1])
{
fprintf(fout,"0\n");
return 0;
}
for (int i=ln-1;i>=0;--i)
expH = (expH + pw[ln-i-1]*a[i]) % MOD;
for (int i=ln-1;i>=0;--i)
currH = (currH + pw[ln-i-1]*b[i]) % MOD;
if (expH == currH)
ans.push_back(1);
for (int i=ln;b[i];++i)
{
currH = (currH - pw[ln-1]*b[i-ln]) % MOD;
if (currH < 0) currH = MOD + currH;
currH = (currH * pww + b[i]) % MOD;
if (expH == currH)
{
ans.push_back(i-ln+1);
if (ans.size() == 1000) break;
}
}
fprintf(fout,"%d\n",ans.size());
if (ans.size())
{
for (auto x:ans)
fprintf(fout,"%d ", x);
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}