Pagini recente » Cod sursa (job #3125897) | Cod sursa (job #1521894) | Cod sursa (job #1860589) | Cod sursa (job #1963361) | Cod sursa (job #2750705)
#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 * 62 % MOD, pw2 = pw2 * 62 % P;
for (int i = 0; i < n; ++i) {
orig = (orig * 62 + cod[a[i]]) % MOD;
orig2 = (orig2 * 62 + cod[a[i]]) % P;
cur = (cur * 62 + cod[b[i]]) % MOD;
cur2 = (cur2 * 62 + 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) * 62 + cod[b[i]]) % MOD;
cur2 = ((cur2 - cod[b[i - n]] * pw2 % P + P) * 62 + 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;
}