Cod sursa(job #1773995)

Utilizator CTI_KnightCir Constantin CTI_Knight Data 8 octombrie 2016 14:16:43
Problema Potrivirea sirurilor Scor 40
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[s.size() + 2];
    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' ;
    for (vector <int>::iterator it = answer.begin(); it != answer.end(); ++it) {
        g << *it << ' ';
    }

    return 0;
}