Pagini recente » Cod sursa (job #289960) | Cod sursa (job #1470351) | Cod sursa (job #782167) | Cod sursa (job #2156783) | Cod sursa (job #3154755)
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int NMAX = 2e5+2;
const int NRB = 2;
const int MOD = 9999937;
vector<int> baze = {27,69};
int n;
string a,str;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
struct Mint {
int val = 0;
Mint operator + (const Mint &aux) const {
Mint ans;
ans.val = (val + aux.val)%MOD;
return ans;
}
Mint operator - (const Mint &aux) const {
Mint ans;
ans.val = (val - aux.val + MOD)%MOD;
return ans;
}
Mint operator * (const Mint &aux) const {
Mint ans;
ans.val = (val * aux.val)%MOD;
return ans;
}
Mint operator * (int x) const {
Mint ans;
x %= MOD;
ans.val = (val * x)%MOD;
return ans;
}
Mint operator = (int x){
val = x;
return *this;
}
Mint operator = (const Mint &aux){
val = aux.val;
return *this;
}
} prefh[NRB][NMAX], inv[NRB][NMAX];
int lgput(int n, int a){
if(a == 0){
return 1;
}else{
if(a%2 == 0){
int val = lgput(n, a/2);
return (val*val)%MOD;
}else{
return (n*lgput(n, a-1))%MOD;
}
}
}
signed main()
{
fin >> a >> str;
n = str.size();
Mint ha[NRB];
Mint put[NRB];
for(int i = 0; i < NRB; i++){
put[i] = lgput(baze[i], n);
inv[i][n] = lgput(put[i].val, MOD-2);
for(int j = n-1; j >= 0; j--){
inv[i][j] = inv[i][j+1]*baze[i];
}
put[i] = 1;
}
for(char ch: a){
int dig = ch;
for(int i = 0; i < NRB; i++){
ha[i] = ha[i] + (put[i]*dig);
}
for(int i = 0; i < NRB; i++){
put[i] = put[i]*baze[i];
}
}
for(int i = 0; i < NRB; i++){
put[i] = 1;
}
Mint hstr[NRB];
for(int i = 0; i < str.size(); i++){
for(int j = 0; j < NRB; j++){
int dig = str[i];
hstr[j] = hstr[j] + (put[j]*dig);
prefh[j][i] = hstr[j];
put[j] = put[j]*baze[j];
}
}
int cnt = 0;
vector<int> sol;
for(int i = a.size()-1, scad = 0; i < str.size(); i++, scad++){
/// checking [i-a.size()+1, i]
int l = i-a.size()+1, r = i;
bool ok = true;
for(int j = 0; j < NRB; j++){
Mint h;
h = (prefh[j][r] - prefh[j][l-1]) * inv[j][scad];
if(h.val != ha[j].val){
ok = false;
break;
}
}
if(ok){
if(sol.size()+1 <= 1000)
sol.push_back(l);
cnt++;
}
}
fout << cnt << "\n";
for(int it: sol){
fout << it << " ";
}
return 0;
}