Cod sursa(job #2099450)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 4 ianuarie 2018 13:56:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const long long  MOD1=100007,MOD2=100021,BAZA=75;
vector <int> v;
string a,b;
long long val1,val2,p1,p2,n,m,rhash1,rhash2;
int main()
{
    fi>>a;
    fi>>b;
    n=a.size();
    m=b.size();
    p1=p2=1;
    for(int i=0;i<n;i++)
    {
        val1=(val1*BAZA+(a[i]-'0'))%MOD1;
        val2=(val2*BAZA+(a[i]-'0'))%MOD2;
        if(i)
        {
            p1=(p1*BAZA)%MOD1;
            p2=(p2*BAZA)%MOD2;
        }
    }
    if(n>m)
    {
        fo<<0;
        fi.close();
        fo.close();
        return 0;
    }
    for(int i=0;i<n;i++)
    {
        rhash1=(rhash1*BAZA+(b[i]-'0'))%MOD1;
        rhash2=(rhash2*BAZA+(b[i]-'0'))%MOD2;
    }
    if(rhash1==val1 && rhash2==val2)
        v.push_back(0);
    for(int i=n;i<m;i++)
    {
        rhash1=(((rhash1-(b[i-n]-'0')*p1)%MOD1+MOD1)*BAZA+(b[i]-'0'))%MOD1;
        rhash2=(((rhash2-(b[i-n]-'0')*p2)%MOD2+MOD2)*BAZA+(b[i]-'0'))%MOD2;
        if(rhash1==val1 && rhash2==val2)
            v.push_back(i-n+1);
    }
    int sol=v.size();
    fo<<sol<<"\n";
    for(int i=0;i<min(sol,1000);i++)
        fo<<v[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}