Cod sursa(job #2808514)

Utilizator stefanlupoi1Lupoi Stefan stefanlupoi1 Data 25 noiembrie 2021 11:23:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 2000005;

char text[N], pattern[N];
int lps[N], ans[1005], cnt;

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

void KMP(){
    int m = strlen(pattern);
    int n = strlen(text);
    int i = 0, j = 0;
    buildLPS(m);
    while(i < n){
        if(pattern[j] == text[i]){
            i++;
            j++;
        }
        if(j == m){
            cnt++;
            if(cnt <= 1000){
                ans[cnt] = i - j;
            }
            j = lps[j - 1];
        }
        else if(i < n and pattern[j] != text[i]){
            if(j != 0){
                j = lps[j - 1];
            }
            else{
                i++;
            }
        }
    }
}

int main()
{
    in.get(pattern, N); in.get();
    in.get(text, N);
    KMP();
    out << cnt << '\n';
    cnt = min(cnt, 1000);
    for(int i = 1; i <= cnt; i++){
        out << ans[i] << " ";
    }
    return 0;
}