Cod sursa(job #3170599)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 17 noiembrie 2023 20:00:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

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

string a, b;
const long long bz=41, MOD1=20000147, MOD2=1000000007;
int n, m;
vector <int> sol;

struct stuts
{
    long long v1=0, v2=0, p1=1, p2=1;

    void next_stuts(char a, char b)
    {
        v1=(v1-(1LL*a*p1)%MOD1+MOD1)%MOD1;
        v1=(v1*bz)%MOD1;
        v1=(v1+1LL*b)%MOD1;

        v2=(v2-(1LL*a*p2)%MOD2+MOD2)%MOD2;
        v2=(v2*bz)%MOD2;
        v2=(v2+1LL*b)%MOD2;
      //  cout << v1 << " " << v2 << endl;
    }

    stuts(int k, string y)
    {
        for (int i=k-1;i>=0;--i)
        {
            //cout << p1 << endl;
            v1=(v1+(p1*y[i])%MOD1)%MOD1;
            v2=(v2+(p2*y[i])%MOD2)%MOD2;
            if (i>0){
            p1=(p1*bz)%MOD1;
            p2=(p2*bz)%MOD2;}
        }

      // cout << v1 << " " << v2 << endl;
    }

    bool operator == (const stuts other)const{
        return (v1==other.v1)&&(v2==other.v2);
    }
};

void solve()
{
    fin>>b>>a;
    int m=b.size(),n=a.size();
    stuts pat(m,b), sir(m,a);
    int c=0;
    for (int i=m-1;i<n;++i)
    {
        if (pat==sir){
            c++;
            sol.push_back(i-m+1);
        }
        sir.next_stuts(a[i-m+1],a[i+1]);
    }
    fout << c << "\n";
    int nr=sol.size();
    for (int i=0;i<min(n,nr);++i)
        fout << sol[i] << " ";
}

int main()
{
    solve();
    return 0;
}