Pagini recente » Cod sursa (job #371305) | Cod sursa (job #2204034) | Cod sursa (job #2989673) | Cod sursa (job #1816078) | Cod sursa (job #2212450)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int d = 256;
string s1, s2;
int n, m, cnt;
vector<int>v;
const int MOD = 666013;
int main()
{
fin >> s1 >> s2;
m = s1.size();
n = s2.size();
int p = 1;
for (int i = 1; i < m; i++) {
p = (p * d) % MOD;
}
int a, b;
a = b = 0;
for (int i = 0; i < m; i++) {
a = (a * d + s1[i]) % MOD;
b = (b * d + s2[i]) % MOD;
}
for (int i = 0; i <= n - m; i++) {
if (a == b) {
bool ok = 1;
for (int j = i; j < i + m; j++)
if (s1[j - i] != s2[j]) {ok = 0; break;}
if (ok) {
cnt++;
v.push_back(i);
if (cnt == 1000) break;
}
}
b = (d * (b - p * s2[i]) % MOD + s2[i + m] + MOD) % MOD;
}
fout << cnt << "\n";
for (int i = 0; i < v.size(); i++)
fout << v[i] << " ";
return 0;
}