Cod sursa(job #3259602)

Utilizator rares89_Dumitriu Rares rares89_ Data 26 noiembrie 2024 21:06:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>

using namespace std;

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

int lps[2000005]; // lps[0] = 0 implicit
vector<int> ans;
int val;

int main() {
    string pattern, word;
    fin >> pattern;
    fin >> word;
    int n = pattern.size(), m = word.length(), len = 0;
    for(int i = 1; i < n; ) {
        if(pattern[i] == pattern[len]) {
            lps[i++] = ++len;
        } else if(len != 0) {
            // Pt a da skip peste caractere
            len = lps[len - 1];
        } else {
            // lps[i] = 0;
            ++i;
        }
    }
    // Folosesc array precalculat pt a verifica in timp liniar
    for(int i = 0, j = 0; i < m; ) {
        if(pattern[j] == word[i]) {
            ++i; ++j;
            if(j == n) {
                ++val;
                if(ans.size() < 1000) {
                    ans.push_back(i - j);
                }
                j = lps[j - 1];
            }
        } else if(j != 0) {
            j = lps[j - 1];
        } else {
            ++i;
        }
    }
    fout << val << "\n";
    for(int x : ans) {
        fout << x << " ";
    }
    return 0;
}