Pagini recente » Cod sursa (job #2010572) | Cod sursa (job #2750184) | Cod sursa (job #1531699) | Cod sursa (job #3278043) | Cod sursa (job #1689909)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define INF numeric_limits<int>::max()
#define int64 long long
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
vector<int> sol;
#define P 3
#define mod1 66013
#define mod2 59657
int main()
{
in>>a>>b;
int N=(int)a.size(),M=(int)b.size(),m1=0,m2=0,c1=1,c2=1;
for(int i=N-1;i>=0;i--)
{
m1=(m1+c1*a[i])%mod1;
m2=(m2+c2*a[i])%mod2;
c1=(c1*P)%mod1;
c2=(c2*P)%mod2;
}
int h1=0,h2=0;
c1=c2=1;
for(int i=N-1;i>=0;i--)
{
h1=(h1+c1*b[i])%mod1;
h2=(h2+c2*b[i])%mod2;
if(i!=0)
{
c1=(c1*P)%mod1;
c2=(c2*P)%mod2;
}
}
if(h1==m1 && h2==m2)
sol.pb(0);
for(int i=N;i<M;i++)
{
h1=((h1-(c1*b[i-N])%mod1+mod1)*P+b[i])%mod1;
h2=((h2-(c2*b[i-N])%mod2+mod2)*P+b[i])%mod2;
if(h1==m1 && h2==m2)
sol.pb(i-N+1);
}
out<<sol.size()<<'\n';
for(int i=0;i<min((int)sol.size(),1000);i++)
out<<sol[i]<<' ';
return 0;
}