Cod sursa(job #2478966)

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

using namespace std;

const int NMAX = 2 * 1e6;

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

int main() {
    FILE *fin = fopen( "strmatch.in", "r" ), *fout = fopen( "strmatch.out", "w" );
    int i, k, x, total;
    i = 1;
    fscanf( fin, " " );
    char ch = fgetc( fin );
    while ( isalpha( ch ) ) {
        s[i] = ch;
        ch = fgetc( fin );
        i ++;
    }
    k = i - 1;
    s[i] = '#';
    i ++;
    fscanf( fin, " " );
    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;
    }
    total = 0;
    for ( i = k; i <= n; i ++ ) {
        if ( kmp[i] == k ) {
            total ++;
        }
    }
    fprintf( fout, "%d \n", total );
    for ( i = k; i <= n; i ++ ) {
        if ( kmp[i] == k ) {
            fprintf( fout, "%d ", i - 2 * k - 1 );
        }
    }
    fclose( fin );
    fclose( fout );
    return 0;
}