Cod sursa(job #1996758)

Utilizator savigunFeleaga Dragos-George savigun Data 2 iulie 2017 15:56:14
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

int n, m, p[4000006], sol[2000005];
char a[4000006];

void kmp() {
    int j = 0;
    int i = 1;

    while (i < m) {
        if (a[i] == a[j]) {
            p[i] = j + 1;
            if (p[i] == n) {
                sol[++sol[0]] = i;
            }
            i++;
            j++;

        } else {
            if (j == 0) {
                p[i] = 0;
                i++;
            } else {
                j = p[j - 1];
            }
        }
    }
}


int main()
{
    in >> a;
    n = strlen(a);

    a[n] = '#';
    in >> (a + n + 1);

    m = strlen(a);

    kmp();

    out << sol[0] << "\n";

    for (int i = 1; i <= sol[0]; ++i) {
        out << sol[i] - n - n << " ";
    }

    return 0;
}