Cod sursa(job #900266)

Utilizator rootsroots1 roots Data 28 februarie 2013 18:45:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream cin;
ofstream cout;

string a, b;
vector < int > pre;
vector < int > sol;

int main()
{
    cin.open("strmatch.in");
    cout.open("strmatch.out");

    getline(cin, a);
    getline(cin, b);

    pre.push_back( - 1);
    int q = - 1;
    for(int i = 1; i < a.size(); ++ i)
    {
        while(q > - 1 && a[i] != a[q + 1]) q = pre[q];
        if(a[i] == a[q + 1]) ++ q;
        pre.push_back(q);
    }

    q = - 1;
    for(int i = 0; i < b.size(); ++ i)
    {
        while(q > - 1 && b[i] != a[q + 1]) q = pre[q];
        if(b[i] == a[q + 1]) ++ q;
        if(q + 1 == a.size()) sol.push_back(i - q);
    }

    cout << sol.size() << '\n';
    for(int i = 0; i < 1000 && i < sol.size(); ++ i)
        cout << sol[i] << ' ';
    cout << '\n';

    cin.close();
    cout.close();

    return 0;
}