Pagini recente » Cod sursa (job #2539516) | Cod sursa (job #2608685) | Cod sursa (job #343481) | Cod sursa (job #629995) | Cod sursa (job #3199723)
#include<bits/stdc++.h>
#define ll long long
#define m1 1000000007
#define m2 1000000013
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<ll> v;
ll p1=1,p2=1;
int main()
{in>>a>>b;
if(a.size()>b.size()) {
out<<0;
return 0;
}
ll h1=0,h2=0;
for(ll i=0;i<a.size();i++) {
h1=(h1*31%m1+a[i])%m1;
h2=(h2*37%m2+a[i])%m2;
if(i) p1=(p1*31)%m1,p2=(p2*37)%m2;
}
ll H1=0,H2=0;
for(ll i=0;i<a.size();i++) {
H1=(H1*31%m1+b[i])%m1;
H2=(H2*37%m2+b[i])%m2;
}
if(h1==H1 && h2==H2) v.push_back(0);
for(ll i=a.size();i<b.size();i++) {
H1=(((H1+m1-(b[i-a.size()]*p1%m1))*31)%m1+b[i])%m1;
H2=(((H2+m2-(b[i-a.size()]*p2%m2))*37)%m2+b[i])%m2;
if(h1==H1 && h2==H2) v.push_back(i-a.size()+1);
}
out<<v.size()<<'\n';
for(ll i=0;i<v.size() && i<1000;i++)
out<<v[i]<<' ';
return 0;
}