Pagini recente » Cod sursa (job #2688033) | Cod sursa (job #1697656) | Cod sursa (job #2866933) | Cod sursa (job #838784) | Cod sursa (job #1933831)
#include <bits/stdc++.h>
using namespace std;
const int mod1 = 100007;
const int mod2 = 100021;
const int wut = 131;
int h1, h2;
int a1, a2;
vector<int> ret;
int main()
{
ifstream f("strmatch.in");
FILE *g = fopen("strmatch.out", "w");
string A; f >> A;
int n = A.size();
string B; f >> B;
int m = B.size();
if(n > m) {
fprintf(g, "0\n");
return 0;
}
int p1 = 1, p2 = 1;
h1 = A[0];
h2 = A[0];
for(int i = 1; i < n; i ++) {
p1 = (p1 * wut) % mod1;
p2 = (p2 * wut) % mod2;
h1 = (h1 * wut + A[i]) % mod1;
h2 = (h2 * wut + A[i]) % mod2;
}
for(int i = 0; i < n; i ++) {
a1 = (a1 * wut + B[i]) % mod1;
a2 = (a2 * wut + B[i]) % mod2;
}
if(a1 == h1 && a2 == h2) {
ret.push_back(0);
}
for(int i = n; i < m; i ++) {
a1 = ((a1 - (B[i - n] * p1) % mod1 + mod1) * wut + B[i]) % mod1;
a2 = ((a2 - (B[i - n] * p2) % mod2 + mod2) * wut + B[i]) % mod2;
if(a1 == h1 && a2 == h2) {
ret.push_back(i - n + 1);
}
}
int l = min(1000, (int)ret.size());
fprintf(g, "%d\n", l);
for(int i = 0; i < l; i ++) fprintf(g, "%d ", ret[i]);
fprintf(g, "\n");
return 0;
}