Cod sursa(job #3215779)

Utilizator DomnulMilandruMilandru Nicon-David DomnulMilandru Data 15 martie 2024 12:45:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb

#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001],B[2000001];
const int M1=100007;
const int M2=100021;
long P1=1,P2=1;
long long hash1A,hash1B;
long long hash2A,hash2B;
int NA,NB;
vector<int> ans;
int main()
{
    cin>>A>>B;
    NA=strlen(A);
    NB=strlen(B);
    if(NA>NB)
    {
        cout<<0;
        return 0;
    }
    for(int i=0;i<NA;i++)
    {
        hash1A=(hash1A*256+A[i])%M1;
        hash1B=(hash1B*256+B[i])%M1;
        hash2A=(hash2A*256+A[i])%M2;
        hash2B=(hash2B*256+B[i])%M2;

        if(i)
        {
            P1=(P1*256*1LL)%M1;
            P2=(P2*256*1LL)%M2;
        }
    }
    if(hash1A==hash1B && hash2A==hash2B)
        ans.push_back(0);
    for(int i=1;i<=NB-NA;i++)
    {

        hash1B=((((hash1B-B[i-1]*P1)%M1+M1)*256%M1)+B[i+NA-1])%M1;
        hash2B=((((hash2B-B[i-1]*P2)%M2+M2)*256%M2)+B[i+NA-1])%M2;
        if(hash1A==hash1B && hash2A==hash2B)
              ans.push_back(i);
    }
    cout<<ans.size()<<'\n';
    for(int i=0;i<min((int) ans.size(),1000);i++)
      cout<<ans[i]<<" ";
    return 0;
}