Pagini recente » Cod sursa (job #427872) | Cod sursa (job #2683792) | Cod sursa (job #441041) | Cod sursa (job #374345) | Cod sursa (job #2361433)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int P = 26;
const int Mod = 123457;
const int Mod1 = 1000003;
const int Nmax = 2e6 + 5;
char a[Nmax], b[Nmax];
int prod1, prod2, ans[Nmax], d, n, m;
int main()
{
int x, y, xx, yy;
fin >> (a + 1) >> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
if(n > m)
{
fout << "0\n";
return 0;
}
prod1 = prod2 = 1;
x = y = xx = yy = 0;
for(int i = 1 ; i <= n ; i++)
{
x = (x * P + a[i]) % Mod;
y = (y * P + a[i]) % Mod1;
xx = (xx * P + b[i]) % Mod;
yy = (yy * P + b[i]) % Mod1;
if(i == 1)
continue;
prod1 = (prod1 * P) % Mod;
prod2 = (prod2 * P) % Mod1;
}
if(x == xx && y == yy)
ans[++d] = 0;
for(int i = n + 1 ; i <= m; i++)
{
xx = ((xx - (b[i - n] * prod1) % Mod + Mod) % Mod * P + b[i]) % Mod;
yy = ((yy - (b[i - n] * prod2) % Mod1 + Mod1) % Mod1 * P + b[i]) % Mod1;
///cout << x << " " << y << " " << xx << " " << yy << " " << i - n << "\n";
if(x == xx && y == yy)
ans[++d] = i - n;
}
fout << d << "\n";
for(int i = 1 ; i <= min(d , 1000) ; i++)
fout << ans[i] << " ";
fout << "\n";
fin.close();
fout.close();
return 0;
}