Cod sursa(job #2705757)

Utilizator proflaurianPanaete Adrian proflaurian Data 13 februarie 2021 11:33:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int P = 666013;
const int M = 1000000007;
string A,B;
int n,m,p=1,codA,codB,cnt;
vector<int> poz;
int main()
{
    f>>A>>B;
    n=A.size();
    m=B.size();
    codA=A[0];
    codB=B[0];
    for(int i=1;i<n;i++)
    {
        codA=(1LL*codA*P%M+A[i])%M;
        p=1LL*p*P%M;
    }
    for(int i=1;i<n-1;i++)
        codB=(1LL*codB*P%M+B[i])%M;
    for(int st=0,dr=n-1;dr<m;st++,dr++)
    {
        codB=(1LL*codB*P%M+B[dr])%M;
        if(codB==codA)
        {
            cnt++;
            if(cnt<1000)
                poz.push_back(st);
        }
        codB=(1LL*codB-1LL*p*B[st]%M+M)%M;
    }
    g<<cnt<<'\n';
    for(auto it:poz)
        g<<it<<' ';
    return 0;
}