Cod sursa(job #3337495)

Utilizator sankeeeeAndrei Lascu sankeeee Data 28 ianuarie 2026 09:29:26
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

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

vector<int> computeLPS(string &pattern) {
    int n = pattern.size();
    vector<int> lps(n,0);

    int len = 0;
    int i = 1;
    while ( i<n ) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
        } else {
            if (len != 0) {
                len = lps[len-1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }

    return lps;
}

void constructLPS(string &pattern, vector<int> &lps) {
    int len = 0;
    lps[0] = 0;

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

vector<int> search(string &pattern, string &txt) {
    int n = txt.length();
    int m = pattern.length();

    vector<int> lps(m);
    vector<int> res;

    constructLPS(pattern, lps);

    int i = 0;
    int j = 0;

    while ( i < n ) {
        if (txt[i] == pattern[j]) {
            i++;
            j++;
            if (j==m) {
                res.push_back(i-j);
                j=lps[j-1];
            }
        } else {
            if (j!=0)
                j=lps[j-1];
            else
                i++;
        }
    }
    return res;
}
int main() {
    string txt,pat;
    fin>>pat;
    fin>>txt;


    const vector<int> res = search(pat, txt);
    fout<<res.size()<<'\n';
    for (int re : res) fout<<re<<' ';
    return 0;
}