Cod sursa(job #1398084)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 23 martie 2015 22:54:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <cstring>
#define MAX 2000002
using namespace std;

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

string A, B;
int p[MAX], poz[MAX], n, m, k, cnt;

int main()
{
    getline(is, A);
    getline(is, B);

    m = A.length();
    n = B.length();

    for ( int i = 1; i < m; i++ )
    {
        while ( k > 0 && A[i] != A[k] )
            k = p[k-1];
        if ( A[i] == A[k] )
            k++;
        p[i] = k;
    }

    k = 0;

    for ( int i = 0; i < n; i++ )
    {
        while ( k > 0 && A[k] != B[i] )
            k = p[k-1];
        if ( A[k] == B[i] )
            k++;
        if ( k == m )
            poz[cnt++] = i - m + 1;
    }

    if ( cnt >= 1000 )
        cnt = 1000;
    os << cnt << '\n';
    for( int i = 0; i < cnt; i++ )
        os << poz[i] << ' ';

    is.close();
    os.close();
    return 0;
}