Cod sursa(job #2721621)

Utilizator vladm98Munteanu Vlad vladm98 Data 12 martie 2021 00:43:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int zValue[4000005];
int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    int cnt = 0, n, m, left = 1, right = 1;
    string pattern, text, str;
    fin >> pattern >> text;

    str = "$" + pattern + "&" + text;
    n = str.size();
    m = pattern.size();

    for (int i = 1; i < n; ++i) {
        zValue[i] = 0;
    }

    for (int i = 2; i < n; ++i) {
        if (i > right) {
            right = i;
            while(right < n && str[right - left] == str[right]) {
                zValue[i] += 1;
                right += 1;
            }
            if (left + zValue[left] <= i + zValue[i]) {
                left = i;
            }
        } else {
            int k = i - left + 1;
            if (i + zValue[k] < right) {
                zValue[i] = zValue[k];
            } else {
                left = i - 1;
                zValue[i] = right - i;
                while (right < n && str[right - left] == str[right]) {
                    zValue[i] += 1;
                    right += 1;
                }
                if (left + zValue[left] <= i + zValue[i]) {
                    left = i;
                }
            }
        }
    }

    for (int i = m + 2; i < n; ++i) {
        if (zValue[i] == m) {
            cnt += 1;
        }
    }
    fout << cnt << "\n";

    cnt = 0;
    for (int i = m + 2; i < n; ++i) {
        if (zValue[i] == m  && cnt < 1000) {
            cnt += 1;
            fout << i - m - 2<< " ";
        }
    }

    return 0;
}