Cod sursa(job #1776855)

Utilizator DoubleNyNinicu Cristian DoubleNy Data 11 octombrie 2016 20:53:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

vector<int> ans, p;
int n, m, nr;
string a, b;

void Prefix()
{
    int k = 0;
    n = a.size();
    p = vector<int>(n + 1);
    for ( int i = 1; i < n; ++i )
    {
        while ( k > 0 && a[k] != a[i] )
            k = p[k - 1];

        if ( a[i] == a[k] )
            k++;
        p[i] = k;
    }
}
void KMP()
{
    int k = 0;
    m = b.size();
    for (int i = 0; i < m; ++i)
    {
        while( k > 0 && b[i] != a[k] )
            k = p[k - 1];

        if ( b[i] == a[k] )
            ++k;

        if (k == n)
                ans.push_back(i - n + 1);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    cin >> a;
    cin >> b;
    Prefix();
    KMP();
    nr = ans.size();
    cout << nr << '\n';
    for ( int i = 0; i < nr && i < 1000; i++)
        cout << ans[i] << ' ';
    return 0;
}