Pagini recente » Cod sursa (job #814522) | Cod sursa (job #1234416) | Cod sursa (job #302930) | Cod sursa (job #10300) | Cod sursa (job #2750703)
#include <bits/stdc++.h>
#define ll long long
#define MOD 9987671
#define P 9981121
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
ll nr, pw = 1, pw2 = 1, orig, orig2, cur, cur2, cod[130];
vector <ll> pos;
int main() {
fin >> a >> b;
for (int i = '0'; i <= '9'; ++i)
cod[i] = ++nr;
for (int i = 'a'; i <= 'z'; ++i)
cod[i] = ++nr;
for (int i = 'A'; i <= 'Z'; ++i)
cod[i] = ++nr;
ll n = a.size();
for (int i = 1; i < n; ++i)
pw = pw * 64 % MOD, pw2 = pw2 * 64 % P;
for (int i = 0; i < n; ++i) {
orig = orig * 64 % MOD + cod[a[i]] % MOD;
orig2 = orig2 * 64 % P + cod[a[i]] % P;
cur = cur * 64 % MOD + cod[b[i]] % MOD;
cur2 = cur2 * 64 % P + cod[b[i]] % P;
}
if (orig == cur && cur2 == orig2)
pos.push_back(0);
for (int i = n; i < b.size(); ++i) {
cur = ((cur - cod[b[i - n]] * pw % MOD + MOD) * 64 + cod[b[i]]) % MOD;
cur2 = ((cur2 - cod[b[i - n]] * pw2 % P + P) * 64 + cod[b[i]]) % P;
if (cur == orig && cur2 == orig2 && pos.size() < 1000)
pos.push_back(i - n + 1);
}
fout << pos.size() << "\n";
for (int i = 0; i < pos.size(); ++i)
fout << pos[i] << " ";
return 0;
}