Cod sursa(job #2419117)

Utilizator Catalin_GriuGriu Catalin Catalin_Griu Data 7 mai 2019 18:08:48
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 100000000007
#define LMAX 2000003
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string str1;
string str2;

int  r=-1, n,m,i;
unsigned long long k, h1, h2,b;
int rs[1001];

unsigned long long pow(int a, int b)
{
    if(b==0)
        return 1;
    unsigned long long x = pow(a, b/2);
    if(b%2==0)
        return (x*x)%MOD;
    return (x*x*a)%MOD;
}

int main()
{
    fin>>str1>>str2;
    int lp = str1.size()-1;
    n = str1.size();
    m = str2.size();
    b=1;
    for(i=n-1;i>=0; i--)
    {
         k=(k+(str1[i]-'A')*b)%MOD;
        h1+=((str2[i]-'A')*b)%MOD;
        b=(b*31)%MOD;

    }

   /* for(int i=0; i<=lp; i++)
    {
        k+=((str1[i]-'A')*pow(31, lp-i))%MOD;
        h1+=((str2[i]-'A')*pow(31, lp-i))%MOD;
    }*/

    if(k==h1)
        rs[++r]=0;
   // cout<<h1<<' '<<k<<'\n';

    int st;
    int dr;

    for(i=n; i<m; i++)
    {
        //h2=((h1*31)%MOD-((str2[st-1]-'A')*pow(31, lp))%MOD+str2[dr]-'A')%MOD;
        h1=(((h1*31)%MOD-((str2[i-n]-'A')*b)%MOD)%MOD+str2[i]-'A')%MOD;
        h1=(h1+MOD)%MOD;
       // h2*=31;

        if(k==h1 && r<1000)
            rs[++r]=i-n+1;
        else if(k==h2)
            r++;

        //cout<<h1<<'\n';
           }
    r = min(r,999);
    fout<<r+1<<'\n';
    for(i=0; i<=r; i++)
        fout<<rs[i]<<' ';

    return 0;
}