Cod sursa(job #1370140)

Utilizator Juve45UAIC Alexandru Ionita Juve45 Data 3 martie 2015 13:08:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>

#define MOD1 10006667
#define MOD2 10009997
#define P 157

using namespace std;

int n, m;
char a[2000004], b[2000004];
int H1, H2, h1, h2, pp1, pp2;
int ans;
vector <int> sol;

void Andreea()
{
    pp1=1;
    pp2=1;
    for(int i=1; i<n; i++)
    {
        pp1*=P, pp1%=MOD1;
        pp2*=P, pp2%=MOD2;
    }

    for(int i=0; i<n; i++)
    {
        H1=H1*P+a[i];
        H1%=MOD1;
        H2=H2*P+a[i];
        H2%=MOD2;

        h1=h1*P+b[i];
        h1%=MOD1;
        h2=h2*P+b[i];
        h2%=MOD2;
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s %s", &a, &b);
    n=strlen(a);
    m=strlen(b);
    Andreea();

    for(int i=n-1; i<=m; i++)
    {
        if(h1==H1 && h2==H2)
        {
            ans++;
            if(sol.size()<1000)
                sol.push_back(i-n+1);
        }

        h1=( (h1 - pp1 * b[i-n+1]% MOD1 )* P + b[i+1] ) %MOD1;
        if(h1<0) h1+=MOD1;

        h2=( (h2 - pp2 * b[i-n+1]% MOD2 )* P + b[i+1] ) %MOD2;
        if(h2<0) h2+=MOD2;

    }
    cout<<ans<<'\n';
    for(int i=0; i<sol.size(); i++)
        cout<<sol[i]<<" \n"[i==sol.size()];
    return 0;
}