Cod sursa(job #3170491)

Utilizator AlexDavid26Alex Bleotu AlexDavid26 Data 17 noiembrie 2023 18:38:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

char txt[2000005], pat[2000005];
int lps[2000005];
int sol[1005], solutions;

void computeLPS(char pat[], int length) {
    int last = 0;
    lps[last] = 0;

    int i = 1;
    while (i < length) {
        if (pat[i] == pat[last])
            lps[i++] = ++last;
        else {
            if (last != 0)
                last = lps[last - 1];
            else
                lps[i++] = 0;
        }
    }
}

void kmp() {
    int n = strlen(txt);
    int m = strlen(pat);

    computeLPS(pat, m);

    int i = 0, j = 0;
    while (n - i >= m - j) {
        if (txt[i] == pat[j])
            i++, j++;

        if (j == m) {
            sol[solutions++] = i - j;
            j = lps[j - 1];
        } else if (i < n && txt[i] != pat[j]){
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

int main() {
    fin >> pat;
    fin >> txt;

    kmp();

    fout << solutions << "\n";
    for (int i = 0; i < solutions && i < 1000; i++)
        fout << sol[i] << " ";
}