Cod sursa(job #1398043)

Utilizator blackMNaught Kora blackM Data 23 martie 2015 22:22:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

string sub, sir;
vector<int> poz, p;
int cnt;

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

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

    p = vector<int>(n+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.push_back(i-n+1);
    }

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

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