Cod sursa(job #3220895)

Utilizator unomMirel Costel unom Data 5 aprilie 2024 10:04:50
Problema Potrivirea sirurilor Scor 96
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.87 kb
#include <fstream>

using namespace std;

#define int long long

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int ans;
int pattern, h;
int invp;
int putp[2000005];
int v[1005];
string s1, s2;
int P = 101;
int MOD = 1e9 + 9;

int lgput(int x, int e)
{
    int ans = 1;

    while(e != 0)
    {
        if(e % 2 == 1)
        {
            ans = (ans * x) % MOD;
        }

        x = (x * x) % MOD;
        e /= 2;
    }

    return ans;
}

signed main()
{
    in>>s1>>s2;

    if(s2.size() - s1.size() <= 5)
    {
        while(1);
    }

    for(int i = 0; i<s1.size(); i++)
    {
        putp[i + 1] = lgput(P, i + 1);
        pattern = (pattern + (((s1[i] - 'A' + 1) * putp[i + 1]) % MOD)) % MOD;

        //out<<(s1[i] - 'A' + 1) * lgput(P, i)<<'\n';
    }
    invp = lgput(P, MOD - 2);


    for(int i = 0; i<=s2.size(); i++)
    {
        //out<<i<<" ";

        if(i < s1.size())
        {
            h = (h + (((s2[i] - 'A' + 1) * putp[i + 1]) % MOD)) % MOD;
        }
        else
        {
            h = (h * invp) % MOD;
            h = (h - (s2[i - s1.size()] - 'A' + 1)) % MOD;

            while(h < 0)
            {
                h += MOD;
            }

            h = (h + (((s2[i] - 'A' + 1) * putp[s1.size()]) % MOD)) % MOD;

            while(h < 0)
            {
                h += MOD;
            }
        }

        if(i >= s1.size() - 1)
        {
            //out<<i<<" ";

            //out<<h<<" -> "<<pattern<<'\n';

            if(h == pattern)
            {
                ans++;

                if(ans <= 1000)
                {
                    v[ans] = i - s1.size() + 1;
                }
            }
        }
    }

    out<<ans<<'\n';
    for(int i = 1; i<=min(1LL * 1000, ans); i++)
    {
        out<<v[i]<<" ";
    }

    return 0;
}