Pagini recente » Cod sursa (job #2591694) | Cod sursa (job #923372)
Cod sursa(job #923372)
#include <fstream>
#include <cstring>
using namespace std;
static const int MAXN = 2000001, MAXA = 1000, MOD = 666013;
char T[MAXN], P[MAXN];
int A[MAXA], kt;
int pre(char s[], int l, int r) {
int ans = 0;
for(int i = l; i < r; i++) {
ans = (ans * 256 + s[i]) % MOD;
}
return ans;
}
int main() {
int ans = 0, lP, lT, put = 1;
ifstream f("strmatch.in");
f >> P >> T;
f.close();
lP = strlen(P);
lT = strlen(T);
int p = pre(P, 0, lP);
int t = pre(T, 0, lP - 1);
for(int i = 1; i < lP; i++) {
put = (put * 256) % MOD;
}
for(int i = lP - 1; i < lT; i++) {
t = (t * 256 + T[i]) % MOD;
if(p == t) {
if(kt < 1000) A[kt++] = i - lP + 1;
ans++;
}
t = ((t - T[i - lP + 1] * put) % MOD + MOD) % MOD;
}
ofstream g("strmatch.out");
g << ans << endl;
for(int i = 0; i < kt; i++) {
g << A[i] << ' ';
}
g << endl;
g.close();
return 0;
}