Pagini recente » Cod sursa (job #2721569) | Cod sursa (job #1152901) | Cod sursa (job #1404745) | Cod sursa (job #341917) | Cod sursa (job #2946931)
// https://www.infoarena.ro/problema/strmatch
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long x=31, m=1e9;
int main() {
string a, b;
fin>>a>>b;
int n=a.size(), m=b.size();
vector<int> p(max(n,m)+1);
p[0] = 1;
for (int i=1; i<p.size(); ++i) p[i] = (p[i-1]*x)%m;
int a_h=0;
vector<int> b_h(m);
for (int i=1; i<m; ++i) b_h[i] = (b_h[i-1] + ((int)b[i]) * p[i])%m;
for (int i=0; i<n; ++i) a_h = (a_h + ((int)a[i]) * p[i])%m;
vector<int> found;
for (int i=0; i+n-1<m; ++i) {
int curr = (b_h[i+n-1] - (i ? b_h[i-1] : 0) + m)%m;
if (curr==a_h*p[i]%m) found.push_back(i);
}
fout<<found.size()<<endl;
for (int v:found) fout<<v<<" ";
}