Cod sursa(job #2927424)

Utilizator proflaurianPanaete Adrian proflaurian Data 20 octombrie 2022 15:07:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("strmatch.in");

ofstream g("strmatch.out");

const int P = 2;
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();
    if(n>m)
    {
        g<<"0\n";
        return 0;
    }
    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(codA==codB)
        {
            if(cnt<1000)
                poz.push_back(st);
            cnt++;
        }
        codB=(1LL*codB-1LL*p*B[st]%M+M)%M;
    }
    g<<cnt<<'\n';
    for(auto it:poz)
        g<<it<<' ';
    return 0;
}