Pagini recente » Cod sursa (job #889419) | Cod sursa (job #1629316) | Cod sursa (job #2337318) | Cod sursa (job #59851) | Cod sursa (job #2817399)
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 100007,MOD2 = 100021,P = 79;
int ans[1005];
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,hash11 = 0,hash21 = 0,hash12 = 0,hash22 = 0,p1 = 1,p2 = 1,cnt = 0;
string s1,s2;
fin >> s1 >> s2;
n = s1.size();
m = s2.size();
if (n > m) {
fout << 0;
return 0;
}
for (int i = 0;i < n;i++){
hash11 = (hash11 * P + s1[i]) % MOD1;
hash12 = (hash12 * P + s1[i]) % MOD2;
hash21 = (hash21 * P + s2[i]) % MOD1;
hash22 = (hash22 * P + s2[i]) % MOD2;
if (i) {
p1 = p1 * P % MOD1;
p2 = p2 * P % MOD2;
}
}
if (hash12 == hash22 && hash11 == hash21)
ans[++cnt] = 0;
for (int i = n;i < m;i++) {
hash21 = ((hash21 - (s2[i - n] * p1 % MOD1) + MOD1) * P + s2[i]) % MOD1;
hash22 = ((hash22 - (s2[i - n] * p2 % MOD2) + MOD2) * P + s2[i]) % MOD2;
if (hash12 == hash22 && hash11 == hash21) {
cnt++;
if (cnt <= 1000)
ans[cnt] = i - n + 1;
}
}
fout << cnt << '\n';
for (int i = 1;i <= min(cnt, 1000);i++)
fout << ans[i] << " ";
return 0;
}