Cod sursa(job #1689909)

Utilizator bogdanboboc97Bogdan Boboc bogdanboboc97 Data 14 aprilie 2016 17:09:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#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;
}