Cod sursa(job #1398064)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 23 martie 2015 22:37:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

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

string sub, sir;
int poz[2000002], p[2000002];
int cnt;

int main()
{
    getline(is, sub);
    getline(is, sir);

    int k = 0;
    int n, m;
    n = sub.length();
    m = sir.length();

    p[0] = p[1] = 0;

    for( int i = 1; i < n; i++ )
    {
        while( k > 0 && sub[k] != sub[i] )
            k = p[k-1];
        if ( sub[k] == sub[i] )
            k++;
        p[i] = k;
    }
    k = 0;
    for( int i = 0; i < m; i++ )
    {
        while( k > 0 && sub[k] != sir[i] )
            k = p[k-1];
        if ( sub[k] == sir[i] )
            k++;
        if ( k == n )
            poz[cnt++] = i - n + 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;
}