Cod sursa(job #2083064)

Utilizator radarobertRada Robert Gabriel radarobert Data 7 decembrie 2017 00:42:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int MOD = 1000000007;
const int d = 256;

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    string pattern;
    cin >> pattern;
    string text;
    cin >> text;

    int h = 1;
    for (int i = 1; i < pattern.size(); i++)
        h = (1LL * h * d) % MOD;

    int pattern_hash = 0;
    int hash = 0;

    for (int i = 0; i < pattern.size() && i < text.size(); i++)
    {
        pattern_hash = ((1LL * pattern_hash * d) + pattern[i]) % MOD;
        hash = ((1LL * hash * d) + text[i]) % MOD;
    }

    int counter = 0;
    int matches_nr = 0;
    int match[1002];

    for (int i = 0; i <= (int)text.size() - (int)pattern.size(); i++)
    {
        if (hash == pattern_hash)
        {
            /*
            int j = 0;
            for (; j < pattern.size(); j++)
            {
                if (text[i + j] != pattern[j])
                    break;
            }

            if (j == pattern.size())
            {
            */
                matches_nr++;
                if (counter < 1000)
                    match[counter++] = i;
            //}
        }

        //rehash
        hash = (d * (hash - 1LL * h * text[i])) % MOD + text[i + pattern.size()];
        if (hash < 0)
            hash += MOD;
        if (hash >= MOD)
            hash -= MOD;
    }

    cout << matches_nr << '\n';
    for (int i = 0; i < matches_nr && i < 1000; i++)
        cout << match[i] << ' ';
    cout << '\n';

    return 0;
}