Cod sursa(job #2540078)

Utilizator Vlad.Vlad Cristian Vlad. Data 6 februarie 2020 18:39:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <iostream>
#define LMAX 2000002
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int z[2 * LMAX], N;
void makeZarr(string str) {
    N = str.length();
    int l, r;
    l = r = 0;
    for (int i = 1; i < N; ++i) {
        if (i > r) {
            int j = 0;
            r = l = i;
            while (r < N && str[j] == str[r]) {
                ++j;
                ++r;
            }
            r--;
            z[i] = r - l + 1;
        }
        else {
            int k = i - l;
            if (z[k] < r - i) {
                z[i] = z[k];
            }
            else {
                int j = r - i;
                l = i;
                while (r < N && str[j] == str[r]) {
                    ++j;
                    ++r;
                }
                r--;
                z[i] = r - l + 1;
            }
        }
    }
}
int main()
{
    string word, s;
    fin >> word >> s;
    int len = word.length(), con = 0, nr = 0;
    makeZarr(word + "?" + s);
    for (int i = len; i < N; ++i) {
        if (z[i] == len) {
            ++con;
        }
    }
    fout << con << "\n";
    for (int i = len; i < N; ++i) {
        if (z[i] == len) {
            fout << i - len - 1 << " ";
            ++nr;
        }
        if (nr > 5000)
            break;
    }
    return 0;
}