Pagini recente » Cod sursa (job #2695221) | Cod sursa (job #598136) | Clasament sim_oni_2010_ziua1 | Cod sursa (job #1415279) | Cod sursa (job #1653622)
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <numeric>
#include <cstring>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <fstream>
#include <cstdlib>
#include <map>
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
#define bit(x) (-x)&x
#define int64 long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s[2000001],x[2000001];
#define P 101
#define mod1 66013
#define mod2 56797
vector<int> match;
int main()
{
in>>x>>s;
int m=strlen(x),n=strlen(s);
int h1=0,h2=0,p1=1,p2=1;
for(int i=m-1;i>=0;i--)
{
h1=(h1+p1*x[i])%mod1;
h2=(h2+p2*x[i])%mod2;
p1=(p1*P)%mod1;
p2=(p2*P)%mod2;
}
p1=p2=1;
int c1=0,c2=0;
for(int i=m-1;i>=0;i--)
{
c1=(c1+p1*s[i])%mod1;
c2=(c2+p2*s[i])%mod2;
if(i!=0)
{
p1=(p1*P)%mod1;
p2=(p2*P)%mod2;
}
}
if(c1==h1 && c2==h2)
match.pb(1);
for(int i=m;i<n;i++)
{
c1=((c1-(s[i-m]*p1)%mod1+mod1)*P+s[i])%mod1;
c2=((c2-(s[i-m]*p2)%mod2+mod2)*P+s[i])%mod2;
if(c1==h1 && c2==h2)
match.pb(i-m+1);
}
out<<match.size()<<'\n';
for(int i=0;i<min((int)match.size(),1000);i++)
out<<match[i]<<' ';
return 0;
}