Cod sursa(job #1774005)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 8 octombrie 2016 14:24:22
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>

#define NM 2000010

using namespace std;

ifstream f ("strmatch.in");
ofstream g ("strmatch.out");

int* pattern(string s) {
    int *l = new int[NM];
    int i = 1;
    int j = 0;
    l[0] = 0;
    while (i < s.size()) {
        if (s[i] == s[j]) {
            l[i] = ++j;
            ++i;
        } else {
            if (j == 0) {
                l[i] = 0;
                ++i;
            } else {
                j = l[j - 1];
            }
        }
    }

    return l;
}

vector <int> KMP(string t, string s) {
    vector <int> a;
    int *l = pattern(s);
    int i = 0;
    int j = 0;
    while (i < t.size()) {
        if (t[i] == s[j]) {
            ++i;
            ++j;
        }
        if (j == s.size()) {
            a.push_back(i - j);
            j = l[j - 1];
        } else if (i < t.size() && t[i] != s[j]) {
            if (j == 0) {
                ++i;
            } else {
                j = l[j - 1];
            }
        }
    }

    return a;
}

int main()
{
    string s, test;
    f >> s >> test;
    vector <int> answer = KMP(test, s);
    g << answer.size() << '\n' ;
    int l = answer.size();
    int k = min(1000, l);
    for (int i = 0; i < k; ++i) {
        g << answer[i] << ' ';
    }

    return 0;
}