Cod sursa(job #3296465)

Utilizator raulababeiAbabei Raul raulababei Data 12 mai 2025 22:53:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>

using namespace std;

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

string text, pattern;

vector<int> LPS(){
    int m = pattern.size();

    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;

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

    return lps;
}

void KMP(){
    int n = text.size();
    int m = pattern.size();

    vector<int> lps = LPS();
    vector<int> position;

    int i = 0;
    int j = 0;
    while(i < n){
        if(text[i] == pattern[j]){
            i++;
            j++;
        }
        if(j == m){
            position.push_back(i - j);
            j = lps[j - 1];
        }
        else if(i < n && text[i] != pattern[j]){
            if(j != 0){
                j = lps[j - 1];
            }
            else{
                i ++;
            }
        }
    }

    out << position.size() << '\n';
    for(auto i : position){
        out << i << ' ';
    }
}

void citire(){
    in >> pattern;
    in >> text;
}

int main() {
    citire();
    KMP();
    return 0;
}