Cod sursa(job #2857988)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 26 februarie 2022 19:17:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000005
int n, m, cnt, nr, lps[NMAX], ans[NMAX];
char pat[NMAX], txt[NMAX];
void init_lps()
{
    int len = 0, i = 1;
    lps[0] = 0;
    while(i < n){
        if (pat[i] == pat[len]){
            len ++;
            lps[i] = len;
            i ++;
        }else{
            if (len != 0){
                len = lps[len - 1];
            }else{
                lps[i] = 0;
                i++;
            }
        }
    }
}
int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    fgets(pat, sizeof(pat), stdin);
    fgets(txt, sizeof(txt), stdin);
    for ( ; isdigit(pat[n]) || isalpha(pat[n]); n++);
    for ( ; isdigit(txt[m]) || isalpha(txt[m]); m++);
    init_lps();
    int i = 0;
    int j = 0;
    while(i < m){
        if (pat[j] == txt[i]){
            i ++;
            j ++;
        }

        if (j == n){
            cnt ++;
            ans[cnt] = i - j;
            j = lps[j - 1];
        }else if (i < m && pat[j] != txt[i]){
            if (j != 0){
                j = lps[j - 1];
            }else{
                i ++;
            }
        }
    }
    printf("%d\n", cnt);
    for (int i=1;i<=min(1000, cnt);i++){
        printf("%d ", ans[i]);
    }
    printf("\n");
    return 0;
}