Pagini recente » Cod sursa (job #3209933) | Cod sursa (job #2357178) | Cod sursa (job #2631318) | Cod sursa (job #3187089) | Cod sursa (job #2361415)
#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[1005], d, n, m;
int main()
{
int x, y, xx, yy;
fin >> (a + 1) >> (b + 1);
n = strlen(a + 1);
m = strlen(b + 1);
for(int i = 1 ; i <= n ; i++)
if('A' <= a[i] && a[i] <= 'Z')
a[i] = a[i] - 'A' + 'a';
for(int i = 1 ; i <= m ; i++)
if('A' <= b[i] && b[i] <= 'Z')
b[i] = b[i] - 'A' + 'a';
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] - 'a')) % Mod;
y = (y * P + (a[i] - 'a')) % Mod1;
xx = (xx * P + (b[i] - 'a')) % Mod;
yy = (yy * P + (b[i] - 'a')) % 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 && d < 1000 ; i++)
{
xx = ((xx - ((b[i - n] - 'a') * prod1) % Mod + Mod) % Mod * P + (b[i] - 'a')) % Mod;
yy = ((yy - ((b[i - n] - 'a') * prod2) % Mod1 + Mod1) % Mod1 * P + (b[i] - 'a')) % 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 <= d ; i++)
fout << ans[i] << " ";
fout << "\n";
fin.close();
fout.close();
return 0;
}