Cod sursa(job #2721999)

Utilizator LeCapataIustinian Serban LeCapata Data 12 martie 2021 15:42:04
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <string.h>
#define N 2000001
using namespace std;

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

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

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

    int i = 1;
    while(i < n){
        if(path[i] == path[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(path[i] == text[j])
            i++, j++;

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

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

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

    crearePrefix();
    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;
}