Pagini recente » Cod sursa (job #714014) | Cod sursa (job #294421) | Cod sursa (job #520839) | Cod sursa (job #770305) | Cod sursa (job #3249729)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 100076969
int sp[2000005];
int op[2000005];
int ans[1005];
int find_ch(char c){
if(c >= 'a' && c <= 'z')
return c - 'a' + 1;
else if(c >= 'A' && c <= 'Z')
return c - 'A' + 27;
else
return c - '0' + 43;
}
int exprapid(int b, int e){
int ans = 1;
while(e){
if(e & 1){
ans *= b;
ans %= MOD;
}
b *= b;
b %= MOD;
e >>= 1;
}
return ans % MOD;
}
signed main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
cin >> a >> b;
int start = exprapid(71, MOD - 2);
op[0]=1;
op[1] = start;
for(int i = 2; i <= b.size(); i++){
op[i] = (op[i-1] * start) % MOD;
op[i] %= MOD;
}
int nr_special = 0, baza = 71;
for(int i = 0; i < a.size(); i++){
nr_special += (find_ch(a[i])*baza) % MOD;
nr_special %= MOD;
baza *= 71;
baza %= MOD;
}
baza =71;
int cntstop = 0;
for(int i = 1; i <= b.size(); i++){
sp[i] = (sp[i-1] + (find_ch(b[i-1])*baza)%MOD) % MOD;
baza*=71;
baza%=MOD;
}
for(int i = a.size(); i <= b.size(); i++){
int nr_actual;
nr_actual = sp[i] + MOD - sp[i - a.size()];
nr_actual %= MOD;
nr_actual *= op[i - a.size()];
nr_actual%=MOD;
if(nr_actual == nr_special){
ans[cntstop++] = i - a.size();
}
}
cout << cntstop << '\n';
for(int i = 0; i < min(1LL*1000, cntstop); i++){
cout << ans[i] << " ";
}
return 0;
}