Cod sursa(job #3298260)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 28 mai 2025 17:02:49
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

const int d=256;
const int mod=666013;

int h1, h2, k, rez[1005];
string s, t;

int main()
{
    fin >> s >> t;
    int m=s.size();
    int n=t.size();
    int h=1;
    for (int i=0; i<m-1; i++)
        h=(h*d)%mod;
    for (int i=0; i<m; i++)
    {
        h1=(d*h1+s[i])%mod;
        h2=(d*h2+t[i])%mod;
    }
    for (int i=0; i<=n-m; i++)
    {
        if (h1==h2)
        {
            int j;
            for (j=0; j<m; j++)
            {
                if (t[i+j]!=s[j])
                    break;
            }
            if (j==m)
            {
                k++;
                if (k<=1000)
                    rez[k]=i;
            }
        }
        if (i<n-m)
        {
            h2=(d*(h2-t[i]*h)+t[i+m])%mod;
            if (h2<0)
                h2+=mod;
        }

    }
    fout << k << '\n';
    for (int i=1; i<=k; i++)
        fout << rez[i] << ' ';
    return 0;
}