Cod sursa(job #2507546)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 10 decembrie 2019 13:52:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[2000004];
char B[2000004];
long long val,sum,cnt;

int main()
{
    fin.getline(A,2000003);
    fin.getline(B,2000003);
    int a = strlen(A);
    int b = strlen(B);

    ///calc val
    int put=1;
    int p=1;
    for(int i=0; i<a; i++)
    {
        val=(val*26+ A[i]-'A' )%MOD;

        if(i==a-1) p=put;
        put=(put*26)%MOD;

    }
    cout<<val<<" "<<26*26;

    ///calc sum
    put=1;
    for(int i=0; i<a; i++)
    {
        sum=(sum*26+ B[i]-'A' )%MOD;
    }
    if(sum==val)
    {
        cnt++;
    }
    for(int i=a; i<b; ++i)
    {

        sum = sum - (B[i - a] - 'A') * p;
        if(sum < 0)
        {
            sum += MOD;
        }
        sum = (sum * 26 + (B[i] - 'A')) % MOD;
        if(sum==val)
        {
            cnt++;
        }
    }

    fout<<cnt;
    return 0;
}