Cod sursa(job #2738882)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 6 aprilie 2021 14:49:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 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*50  + s1[i]-'0';
        cnt2 =  cnt2*50 + s1[i]-'0';
        cnt1%=MOD1;
        cnt2%=MOD2;
    }
    long long c1 = 0 , c2 = 0 ,p1 = 1, p2 = 1;
    for(i = 0 ; i < n;  i++)
    {
        c1 = c1*50  + s2[i]-'0';
        c2 =  c2*50 + s2[i]-'0';
        c1%=MOD1;
        c2%=MOD2;
        if(n - i - 1)
        {p1= p1*50;
        p1%=MOD1;
        p2*=50;
        p2%=MOD2;}
    }
    int answer = 0 ;
    if(c1 == cnt1 && c2 == cnt2)answer ++,sol.push_back(n-1);
    for(i = n ; i < m; i++)
    {
        c1 -= p1*(s2[i-n]-'0');
        c1 *= 50;
        c1 += s2[i]-'0';
        c1%=MOD1;
        if(c1<0)c1+=MOD1;
        c2 -= p2*(s2[i-n]-'0');
        c2 *= 50;
        c2 += s2[i]-'0';
        c2%=MOD2;
        if(c2<0)c2+=MOD2;
        if(c1 == cnt1 && c2 == cnt2)answer ++,sol.push_back(i);
    }
    cout << answer<<endl;
    for(auto edge : sol)
        cout<<edge - n+1<< " ";
    return 0;
}