Cod sursa(job #2738894)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 6 aprilie 2021 14:55:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.74 kb
#include <bits/stdc++.h>
using namespace std;
const int MOD1 = 1e9+7;
const int MOD2 = 1e9+9;
const int MOD3 = 1e9+13;
const int NMAX = 1e6*2;
char s1[NMAX+6] , s2[NMAX + 6];
vector<int>sol;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(s1,NMAX*2+5,stdin);
    fgets(s2,NMAX*2+5,stdin);
    int n = strlen(s1) , m = strlen(s2) , i;
    --n ;
    --m;
    long long cnt1 = 0  , cnt2 = 0 , cnt3 = 0 ;

    for(i = 0 ; i < n  ;i++)
    {
        cnt1 = cnt1*97  + s1[i]-'0';
        cnt2 =  cnt2*97 + s1[i]-'0';
        cnt3 = cnt3*97  +s1[i]-'0';
        cnt1%=MOD1;
        cnt2%=MOD2;
        cnt3%=MOD3;
    }
    long long c1 = 0 , c2 = 0 ,p1 = 1, p2 = 1,p3=1,c3=0;
    for(i = 0 ; i < n;  i++)
    {
        c1 = c1*97  + s2[i]-'0';
        c2 =  c2*97 + s2[i]-'0';
        c3 = c3*97 + s2[i]-'0';
        c1%=MOD1;
        c2%=MOD2;
        c3%=MOD3;
        if(n - i - 1)
        {p1= p1*97;
        p1%=MOD1;
        p2*=97;
        p2%=MOD2;
        p3*=97;
        p3%=MOD3;}
    }
    int answer = 0 ;
    if(c1 == cnt1 && c2 == cnt2&&c3 == cnt3)answer ++,sol.push_back(n-1);
    for(i = n ; i < m; i++)
    {
        c1 -= p1*(s2[i-n]-'0');
        c1 *= 97;
        c1 += s2[i]-'0';
        c1%=MOD1;
        if(c1<0)c1+=MOD1;
        c2 -= p2*(s2[i-n]-'0');
        c2 *= 97;
        c2 += s2[i]-'0';
        c2%=MOD2;
        if(c2<0)c2+=MOD2;
        c3 -= p3*(s2[i-n]-'0');
        c3 *= 97;
        c3 += s2[i]-'0';
        c3%=MOD3;
        if(c3<0)c3+=MOD3;
        if(c1 == cnt1 && c2 == cnt2&& c3 == cnt3)answer ++,sol.push_back(i);
    }
    cout << answer<<endl;
    for(auto edge : sol)
        cout<<edge - n+1<< " ";
    return 0;
}