Cod sursa(job #2722885)

Utilizator LeCapataIustinian Serban LeCapata Data 13 martie 2021 12:53:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <string.h>
#define N 2000001
using namespace std;

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

int n, m, k;
int lps[N], aparitii[N];
char sir[N], text[N];

void creareLPS(){
    int len = 0;
    lps[0] = 0;

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

void KMP(){
    int i = 0, j = 0;
    while(j < m){
        if(sir[i] == text[j])
            i++, j++;

        if(i == n){
            aparitii[++k] = j - i;
            i = lps[i - 1];

        }
        else if(j < m && sir[i] != text[j]){
            if(i != 0) i = lps[i - 1];
            else j++;
        }
    }
}

int main()
{
    in.getline(sir, N);
    in.getline(text, N);

    n = strlen(sir);
    m = strlen(text);

    creareLPS();
    KMP();

    out<<k<<'\n';
    if(k > 1000) k = 1000;

    for(int i = 1; i <= k; ++i)
        out<<aparitii[i]<<" ";

    in.close();
    out.close();
    return 0;
}