Pagini recente » Cod sursa (job #2567332) | Cod sursa (job #2529261) | Cod sursa (job #2110010) | Cod sursa (job #1249300) | Cod sursa (job #2789472)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MOD1 100007
#define MOD2 100021
#define P 73
long long n, m, h, hp, p1, p2, h1, h2;
int v[1005];
string a, b;
int main() {
getline(fin, a);
getline(fin, b);
n = a.size();
m = b.size();
p1 = p2 = 1;
for (int i=0;i<n;i++){
h = (h * P + a[i]) % MOD1;
hp = (hp * P + a[i]) % MOD2;
if (i != 0){
p1 = (p1 * P) % MOD1;
p2 = (p2 * P) % MOD2;
}
}
if (n > m){
fout << "0\n";
return 0;
}
for (int i=0;i<n;i++){
h1 = (h1 * P + b[i]) % MOD1;
h2 = (h2 * P + b[i]) % MOD2;
}
int ans = 0;
if (h1 == h && h1 == hp){
v[0] = 1;
ans ++;
}
for (int i=n;i<m;i++){
h1 = ((h1 - (b[i-n] * p1) % MOD1 + MOD1) * P + b[i]) % MOD1;
h2 = ((h2 - (b[i-n] * p1) % MOD2 + MOD2) * P + b[i]) % MOD2;
if (h1 == h && h2 == hp)
v[i - n + 1] = 1, ans ++;
}
fout << ans << '\n';
ans = 0;
for (int i=0;i<m && ans < 1000;i++)
if (v[i])
ans ++, fout << i << ' ';
fout << '\n';
return 0;
}