Cod sursa(job #3214247)

Utilizator popuPop Matei Tudor popu Data 13 martie 2024 22:24:18
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

#define ll unsigned long long
#define M 1000000007

using namespace std;

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

string a, b;
ll P = 307, lastBase = 1, c;
vector<int> res;

ll logput(ll x, ll exp)
{
    ll aux = 1;
    while(exp)
    {
        if(exp % 2)
            aux = aux * x % M;
        exp /= 2;
        x = x * x % M;
    }
    return aux;
}

ll makeHash(string s, int start, int stop)
{
    ll rez = 0;
    ll aux = 1;

    for(int i = start; i < stop; i++)
    {
        rez = (rez + (aux * s[i] % M)) % M;
        aux = aux * P % M;
    }

    return rez;
}

bool check(int st)
{
    int i = 0;
    while(i < a.length())
    {
        if(a[i] != b[st])
            return 0;
        i++;
        st++;
    }
    return 1;
}

int main()
{
    fin >> a >> b;

    lastBase = logput(P, a.length() - 1);

    if(a.length() > b.length())
    {
        fout << 0;
        return 0;
    }

    ll hashA = makeHash(a, 0, a.length());
    ll hashB = makeHash(b, 0, a.length());

    for(int i = a.length() - 1; i < b.length(); i++)
    {
        if(hashA == hashB && check(i - a.length() + 1) && res.size() <= 1000)
            res.push_back(i - a.length() + 1);
        else if(res.size() > 1000)
            break;

        hashB = (hashB - b[i - b.length() + 1] + M) % M;
        hashB /= P;
        hashB = (hashB + b[i + 1] * lastBase % M) % M;
    }

    fout << res.size() << '\n';
    for(int i = 0; i < res.size(); i++)
        fout << res[i] << ' ';

    return 0;
}