Cod sursa(job #2481164)

Utilizator Tudor06MusatTudor Tudor06 Data 26 octombrie 2019 15:44:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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 ) || isdigit( ch ) ) {
        s[i] = ch;
        ch = fgetc( fin );
        i ++;
    }
    k = i - 1;
    s[i] = '#';
    i ++;
    fscanf( fin, " " );
    ch = fgetc( fin );
    while ( isalpha( ch ) || isdigit( 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 );
    i = k;
    if ( total > 1000 )
        total = 1000;
    while ( i <= n && total > 0 ) {
        if ( kmp[i] == k ) {
            total --;
            fprintf( fout, "%d ", i - 2 * k - 1 );
        }
        i ++;
    }
    fclose( fin );
    fclose( fout );
    return 0;
}