Cod sursa(job #2807701)

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

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

        if (j == n){
            nr ++;
            if (v.size() < MAXP)
                v.push_back(i-n);
        }
    }*/
    i = j = 0;
    while(i<m){
        while(j>=0 && a[i] != p[j]){
            j = urmator[j];
        }
        i ++;
        j ++;
        if (j == n){
            nr ++;
            if (v.size() < MAXP)
                v.push_back(i - n);
        }
    }
    fout << nr << '\n';
    for (auto it : v){
        fout << it << ' ';
    }
}
int main() {
    fin.getline(a, NMAX);
    fin.getline(b, NMAX);

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

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

    return 0;
}