Cod sursa(job #1109327)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 16 februarie 2014 23:17:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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;
const int MAX_LENGTH = 2000005;

char String[MAX_LENGTH], Pattern[MAX_LENGTH], S[2 * MAX_LENGTH];
int MatchCount;
vector<int> MatchPositions;

vector<int> KMP(char whereToSearch[], char pattern[]) {
    memset(S, 0, sizeof(S));
    strcat(S, pattern);
    strcat(S, "#");
    strcat(S, whereToSearch);
    int n = strlen(S), m = strlen(pattern);
    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] == m - 1)
            matches.push_back(i - 2 * m - 1);
    }
    return matches;
}

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

void Read() {
    assert(scanf("%s\n%s", Pattern, String) == 2);
}

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;
}