Pagini recente » Cod sursa (job #1585503) | Cod sursa (job #3227002) | Cod sursa (job #3127974) | Cod sursa (job #684295) | Cod sursa (job #992175)
Cod sursa(job #992175)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAX = 250100;
long long l1, l2;
char a[MAX], b[MAX];
long long mod1 = 100005, mod2 = 666013;
long long ch1 = 277, ch2 = 281;
long long key1, key2;
int sol;
int soln[1010];
int main() {
fin.getline(a + 1, MAX - 1);
fin.getline(b + 1, MAX - 1);
l1 = strlen(a + 1);
l2 = strlen(b + 1);
for (int i = 1; i <= l1; ++i) {
key1 = key1 * ch1 + a[i];
key1 = key1 % mod1;
key2 = key2 * ch2 + a[i];
key2 = key2 % mod2;
}
long long p1, p2; p1 = p2 = 1;
for (int i = 1; i <= l1; ++i)
p1 = (p1 * ch1) % mod1, p2 = (p2 * ch2) % mod2;
long long c1, c2; c1 = c2 = 0;
for (int i = 1; i <= l2; ++i) {
c1 = c1 * ch1 + b[i];
c1 = c1 % mod1;
c2 = c2 * ch2 + b[i];
c2 = c2 % mod2;
if (i > l1) {
c1 = (c1 - p1 * b[i - l1]) % mod1;
if (c1 < 0)
c1 += mod1;
c2 = (c2 - p2 * b[i - l1]) % mod2;
if (c2 < 0)
c2 += mod2;
}
if (c1 == key1 && c2 == key2) {
++sol;
if (sol <= 1000)
soln[sol] = i - l1;
}
}
fout << sol << '\n';
for (int i = 1; i <= min(sol, 1000); ++i)
fout << soln[i] << ' ';
}