Cod sursa(job #2803276)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 19 noiembrie 2021 18:53:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMAX 2000005
char a[NMAX], b[NMAX];
int n, m, urmator[NMAX];
void init_urm(char *p)
{
    int i, j;
    urmator[0] = -1;
    for (i=0, j=-1;i<m;i++,j++,urmator[i]=j){
        while(j>=0 && p[i] != p[j]){
            j = urmator[j];
        }
    }
}
int ans[1005];
void kmp(char *a, char *p)
{
    int i, j, nr = 0;
    for (i=0,j=0;j<m && i<n;i++, j++){
        while(j >= 0 && a[i] != p[j]){
            j = urmator[j];
        }

        /*if (p[j] == a[i])
            j ++;*/

        if (j == m - 1){
            //fout << j << ' ';
            j = urmator[j];
            if (nr <= 999){
                ans[++nr] = i - m + 1;
            }else{
                break;
            }
        }
    }
    fout << nr << '\n';
    for (int i=1;i<=nr;i++){
        fout << ans[i] << ' ';
    }
}
int main() {
    fin.getline(b, NMAX);
    fin.getline(a, NMAX);

    n = strlen(a);
    m = strlen(b);

    init_urm(b);
    kmp(a, b);

    return 0;
}