Cod sursa(job #3220892)

Utilizator unomMirel Costel unom Data 5 aprilie 2024 10:03:39
Problema Potrivirea sirurilor Scor 72
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <fstream>

using namespace std;

#define int long long

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int ans;
int pattern1, pattern2;
int h1, h2;
int invp1, invp2;
int putp1[2000005];
int putp2[2000005];
int v[1005];
string s1, s2;
int P = 73;
int MOD1 = 1e9 + 9;
int MOD2 = 2000000011;

int lgput(int x, int e, int MOD)
{
    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;

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

        putp2[i + 1] = lgput(P, i + 1, MOD2);
        pattern2 = (pattern2 + (((s1[i] - 'A' + 1) * putp2[i + 1]) % MOD2)) % MOD2;
    }
    invp1 = lgput(P, MOD1 - 2, MOD1);
    invp2 = lgput(P, MOD2 - 2, MOD2);


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

        if(i < s1.size())
        {
            h1 = (h1 + (((s2[i] - 'A' + 1) * putp1[i + 1]) % MOD1)) % MOD1;
            h2 = (h2 + (((s2[i] - 'A' + 1) * putp2[i + 1]) % MOD2)) % MOD2;
        }
        else
        {
            h1 = (h1 * invp1) % MOD1;
            h1 = (h1 - (s2[i - s1.size()] - 'A' + 1)) % MOD1;

            h2 = (h2 * invp2) % MOD2;
            h2 = (h2 - (s2[i - s1.size()] - 'A' + 1)) % MOD2;

            while(h1 < 0)
            {
                h1 += MOD1;
            }
            while(h2 < 0)
            {
                h2 += MOD2;
            }

            h1 = (h1 + (((s2[i] - 'A' + 1) * putp1[s1.size()]) % MOD1)) % MOD1;
            h2 = (h2 + (((s2[i] - 'A' + 1) * putp2[s1.size()]) % MOD2)) % MOD2;

            while(h1 < 0)
            {
                h1 += MOD1;
            }
            while(h2 < 0)
            {
                h2 += MOD2;
            }
        }

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

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

            if(h1 == pattern1 && h2 == pattern2)
            {
                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;
}