Cod sursa(job #3170466)

Utilizator raulababeiAbabei Raul raulababei Data 17 noiembrie 2023 18:10:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <bits/stdc++.h>

using namespace std;

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

char str[2000000], pattern[2000000];
int n, m;
int P[2000000];
int jis[2000000];
int r;

void getP() {
    int j = 0;
    for(int i = 2;i <= m;i++){
        while(j > 0 && pattern[i] != pattern[j + 1]){
            j = P[j];
        }
        if(pattern[i] == pattern[j + 1]){
            j++;
        }
        P[i] = j;
    }
}

int counter = 0;

void kmp(){
    int j;
    for(int i = 1;i <= n;i++){
        while(j > 0 && pattern[j] != str[i]){
            j = P[j - 1] + 1;
        }
        j++;
        if(j == m + 1){
            counter ++;
            jis[r++] = i - j + 1;
            j = P[j - 1] + 1;
        }
    }
}

int main() {
    in.getline(pattern, 100);
    in.getline(str, 100);
    n = strlen(str) + 1;
    m = strlen(pattern) + 1;
    for(int i = n;i >= 1;i--){
        str[i] = str[i - 1];
    }
    for(int i = m;i >= 1;i--){
        pattern[i] = pattern[i - 1];
    }
    str[0] = pattern[0] = ' ';
    P[0] = -1;
    n--;
    m--;
    getP();
    kmp();
    out << counter << '\n';
    for(int i = 0;i < r;i++){
        out << jis[i] << ' ';
    }
    return 0;
}