Cod sursa(job #1305051)

Utilizator xtreme77Patrick Sava xtreme77 Data 29 decembrie 2014 15:17:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <cstring>

const char IN [ ] = "strmatch.in";
const char OUT [] = "strmatch.out";

using namespace std;

const int kNMax = 2000200;

char P[kNMax], S[kNMax], x[2 * kNMax];
int pref[2 * kNMax];

int main()
{
    ifstream fin(IN);
    ofstream fout(OUT);

    fin >> (P + 1) >> (S + 1);
    int m = strlen(P + 1);
    int n = strlen(S + 1);

    for (int i = 1; i <= m; ++i)
        x[i] = P[i];
    int len = m;
    x[++len] = '$';
    for (int i = 1; i <= n; ++i)
        x[++len] = S[i];

    for (int i = 2; i <= len; ++i) {
        int suf = pref[i - 1];
        while (1) {
            if (x[suf + 1] == x[i]) {
                ++suf;
                break;
            }
            if (suf == 0)
                break;
            suf = pref[suf];
        }
        pref[i] = suf;
    }

    int res = 0;
    for (int i = m + 2; i <= len; ++i)
            if (pref[i] == m)
                ++res;
    fout << res << "\n";

    int cnt = 0;
    for (int i = m + 2; cnt < 1000 && i <= len; ++i)
        if (pref[i] == m) {
                fout << i - m + 1  - (m + 1) - 1<< " ";
                ++cnt;
        }
    return 0;
}