Cod sursa(job #1386959)

Utilizator vasica38Vasile Catana vasica38 Data 13 martie 2015 16:24:17
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<fstream>
#include<algorithm>
#define  mod1 1000021
#define  mod2 100007
#define  p 73

using namespace std;

string s1,s2;

int sol[1001];

int i,j,k,m,n,u;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    getline(cin,s1);
    getline(cin,s2);
    //cout<<s2;
    n=s1.size()-1;
    m=s2.size()-1;
    int hash1,hash2,p1,hash3,hash4,p2;
    hash3=hash4=hash1=hash2=0;
    p1=1;
    p2=1;
    for (i=0; i<n; ++i)
    {
        hash1=(hash1*p+s1[i])%mod1;
        hash2=(hash2*p+s1[i])%mod2;
        hash3=(hash3*p+s2[i])%mod1;
        hash4=(hash4*p+s2[i])%mod2;
        if (i>0)
            {
                p1=(p1*p)% mod1;
                p2=(p2*p)% mod2;
            }
    }
    if (hash1==hash3 && hash2==hash4) sol[++u]=0;
    for (i=n; i<m; ++i)
    {
        hash3=((hash3-((s2[i-n]*p1)%mod1)+mod1)*p+s2[i])%mod1;
        hash4=((hash4-((s2[i-n]*p2)%mod2)+mod2)*p+s2[i])%mod2;

        if (hash1==hash3 && hash2==hash4) sol[++u]=i-n+1;
    }
    cout<<u<<"\n";
    for (i=1; i<=min(u,1000); ++i) cout<<sol[i]<<" ";




    return 0;
}