Pagini recente » Cod sursa (job #2233829) | Cod sursa (job #1058885) | Statistici Leoveanu Bianca (Biencutza04) | Cod sursa (job #970246) | Cod sursa (job #3202868)
// #include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
#define MOD1 100007
#define MOD2 100021
#define PRIM 73
int match[2000001];
int main()
{
string main, pattern;
getline(cin, pattern);
getline(cin, main);
int nm = main.size();
int np = pattern.size();
if (np > nm)
{
cout << 0;
return 0;
}
int p1, p2, h1, h2, hp1, hp2;
p1 = p2 = 1;
h1 = h2 = hp1 = hp2 = 0;
for (int i = 0; i < np; i++)
{
hp1 = (hp1 * PRIM + pattern[i]) % MOD1;
hp2 = (hp2 * PRIM + pattern[i]) % MOD2;
h1 = (h1 * PRIM + main[i]) % MOD1;
h2 = (h2 * PRIM + main[i]) % MOD2;
if (i)
{
p1 = (p1 * PRIM) % MOD1;
p2 = (p2 * PRIM) % MOD2;
}
}
int n = 0;
if (h1 == hp1 && h2 == hp2)
match[n++] = 0;
for (int i = 1; i <= nm - np; i++)
{
h1 = (((h1 - main[i - 1] * p1) % MOD1 + MOD1) * PRIM + main[i + np - 1]) % MOD1;
h2 = (((h2 - main[i - 1] * p2) % MOD2 + MOD2) * PRIM + main[i + np - 1]) % MOD2;
if (h1 == hp1 && h2 == hp2)
match[n++] = i;
}
cout << n << '\n';
if (n > 1000)
for (int i = 0; i < 1000; i++)
cout << match[i] << ' ';
else
for (int i = 0; i < n; i++)
cout << match[i] << ' ';
return 0;
}