Cod sursa(job #2478945)

Utilizator Tudor06MusatTudor Tudor06 Data 22 octombrie 2019 22:04:13
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <stdio.h>
#include <ctype.h>

using namespace std;

int const NMAX = 2 * 1e6;

int kmp[NMAX * 2 + 2];
int s[NMAX * 2 + 2];

int main() {
    FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
    int i, k, x;
    i = 1;
    char ch = fgetc( fin );
    while ( isalpha( ch ) ) {
        s[i] = ch;
        ch = fgetc( fin );
        i ++;
    }
    k = i - 1;
    printf( "%d ", k );
    s[i] = '#';
    i ++;

    ch = fgetc( fin );
    while ( isalpha( ch ) ) {
        s[i] = ch;
        ch = fgetc( fin );
        i ++;
    }
    int n = i - 1;
    for ( i = 2; i <= n; i ++ ) {
        x = kmp[i - 1];
        while ( x > 0 && s[x + 1] != s[i] )
            x = kmp[x];
        if ( s[i] == s[x + 1] )
            kmp[i] = x + 1;
    }
    for ( i = k; i <= n; i ++ ) {
        if ( kmp[i] == k ) {
            fprintf( fout, "%d ", i - 2 * k - 1 );
        }
    }
    fclose( fin );
    fclose( fout );
    return 0;
}