Cod sursa(job #1109321)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 16 februarie 2014 23:13:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

typedef long long int64;

const int oo = 0x3f3f3f3f;
const int MAX_MATCHES = 1000;

string String, Pattern;
int MatchCount;
vector<int> MatchPositions;

vector<int> KMP(const string &whereToSearch, const string &pattern) {
    string S = pattern + "#" + whereToSearch;
    int n = int(S.length());
    vector<int> pi = vector<int>(n, -1), matches;
    for (int i = 1, p = -1; i < n; ++i) {
        for (; p != -1 && S[p + 1] != S[i]; p = pi[p]);
        if (S[p + 1] == S[i])
            ++p;
        pi[i] = p;
        if (pi[i] == int(pattern.length()) - 1)
            matches.push_back(i - 2 * int(pattern.length()) - 1);
    }
    return matches;
}

void Solve() {
    MatchPositions = KMP(String, Pattern);
    MatchCount = int(MatchPositions.size());
    MatchPositions.resize(min(MatchCount, MAX_MATCHES));
}

void Read() {
    cin >> Pattern >> String;
}

void Print() {
    cout << MatchCount << "\n";
    for (int i = 0; i < int(MatchPositions.size()); ++i)
        cout << MatchPositions[i] + 1 << " ";
    cout << "\n";
}

int main() {
    assert(freopen("strmatch.in", "r", stdin));
    assert(freopen("strmatch.out", "w", stdout));
    Read();
    Solve();
    Print();
    return 0;
}