Pagini recente » Cod sursa (job #1863552) | Cod sursa (job #1964972) | Cod sursa (job #1212470) | Cod sursa (job #1513871) | Cod sursa (job #3199732)
#include<bits/stdc++.h>
#define ll long long
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=a[0],h2=a[0];
for(ll i=1;i<a.size();i++) {
h1=h1*31+a[i],h2=h2*37+a[i];
p1=p1*31,p2=p2*37;
}
ll H1=0,H2=0;
for(ll i=0;i<a.size();i++)
H1=H1*31+b[i],H2=H2*37+b[i];
if(h1==H1 && h2==H2) v.push_back(0);
for(ll i=a.size();i<b.size();i++) {
H1=(H1-b[i-a.size()]*p1)*31+b[i];
H2=(H2-b[i-a.size()]*p2)*37+b[i];
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;
}