Cod sursa(job #2808332)

Utilizator TeodorMarciucMarciuc Teodor TeodorMarciuc Data 24 noiembrie 2021 21:57:15
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
int lps[2000003], i, n, m, k, j, l, len, v[500005], cnt;
string pat, text;
int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> pat;
    cin >> text;
    lps[0] = 0;
    n = pat.size();
    len = 0;
    i = 1;
    while (i < n) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else if (len != 0) {
            len = lps[len - 1];
        }
        else {
            lps[i] = 0;
            i++;
        }
    }
    m = text.size();
    i = 0;
    while (i < m) {
        if (pat[j] == text[i]) {
            i++;
            j++;
        }
        if (j == n) {
            v[++cnt] = i - n;
            j = lps[j - 1];
        }
        else if (pat[j] != text[i] and i<m) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
    cout << cnt << '\n';
    if (cnt > 1000) cnt = 1000;
    for (i = 1;i <= cnt;i++)
        cout << v[i] << " ";
}