Cod sursa(job #2589310)

Utilizator ovidiu.gaborGabor Ovidiu ovidiu.gabor Data 26 martie 2020 09:38:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <string.h>
#include <algorithm>
#include <fstream>
using namespace std;
void prefix(char t[], int pi[]) {
    int n = strlen(t);
    int k = 0;
    pi[0] = 0;
    for (int i = 1; i < n; i++) {
        k = pi[i - 1];
        while ((k > 0) && (t[k] != t[i]))
        {
            k = pi[k-1];
        }
        if (k == 0) {
            if (t[k] != t[i])
                pi[i] = 0;
            else
                pi[i] = 1;
        }
        else
            pi[i] = k + 1;
    }
    int i;
}
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int v[200001], poz[200001];
void KMP(char s[], char t[]) {
    int n = strlen(s);
    int m = strlen(t);
    int q = 0;
    s[n] = '#';
    s[n + 1] = NULL;
    int i, j;
    for (i = n + 1, j = 0; j <= m; i++, j++)
        s[i] = t[j];
    prefix(s, v);
    m = strlen(s);
    int nr = 0;
    for(int i=2*n;i<m;i++)
        if (v[i] == n) {
            nr++;
           poz[nr] = i-2*n;
        }
    g << nr << endl;
    for (int i = 1; i <= min(1000,nr); i++)
        g << poz[i] << " ";
}

char a[200001], b[200001];
int main()
{
    f >> a;
    f >> b;
     KMP(a, b);
}