Cod sursa(job #820573)

Utilizator GumiPipeNoName GumiPipe Data 21 noiembrie 2012 01:09:00
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
// bullcrap code, chaos
#include <string>
#include <iostream>
#include <vector>

using namespace std;

vector<int> prf;

int kmp(string n, string m)
{
    int ln = n.size();
    int lm = m.size();
    int k;
    prf.resize(ln);

    prf[0] = -1;
    k = -1;
    for (int i = 1; i < ln; ++i)
    {
        while (k > -1 && n[k + 1] != n[i])
            k = prf[k];
        if (n[k + 1] == n[i])
            ++k;
        prf[i] = k;
    }

    k = -1;
    for (int i = 0; i < lm; ++i)
    {
        while (k > -1 && n[k + 1] != m[i])
            k = prf[k];
        if (n[k + 1] == m[i])
            ++k;
        if (k == ln - 1)
        {
            return i - k;
        }
    }

    return -1;
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    string n, m;
    int i, r;
    int v[1000];

    cin >> n >> m;

    for (r = 0, i = 0; i < 1000; ++i)
    {
        r = kmp(n, m);
        if (r == -1) break;
        v[i] = r;
        m = m.substr(r + 1);
    }

    cout << i << endl;
    int p = 0;
    for (int j = 0; j < i; ++j)
    {
        if (j == 0) 
        {
            cout << v[j] << " ";
            p = v[j];
        }
        else
        {
            p += v[j] + 1;
            cout << p << " ";
        }
    }
    
    fclose(stdin);
    return 0;
}