Cod sursa(job #785703)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 9 septembrie 2012 18:23:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MaxN = 2000005;

int N, M, Z[MaxN], Match[MaxN];
vector<int> MatchPos;
char Pattern[MaxN], String[MaxN];

void BuildZ() {
    Z[1] = 0;
    int Pos = 1, Right = 1;
    for (int i = 2; i <= M; ++i) {
        if (i <= Right)
            Z[i] = min(Right-i+1, Z[i-Pos+1]);
        for (; i+Z[i] <= M && Pattern[Z[i]+1] == Pattern[i+Z[i]]; ++Z[i]);
        if (i+Z[i]-1 > Right)
            Pos = i, Right = i+Z[i]-1;
    }
}

void PatternMatch() {
    int Pos = 0, Right = 0;
    for (int i = 1; i <= N; ++i) {
        if (i <= Right)
            Match[i] = min(Right-i+1, Z[i-Pos+1]);
        for (; Match[i] < M && i+Match[i] <= N && Pattern[Match[i]+1] == String[i+Match[i]]; ++Match[i]);
        if (i+Match[i]-1 > Right)
            Pos = i, Right = i+Match[i]-1;
        if (Match[i] == M)
            MatchPos.push_back(i-1);
    }
}

void Solve() {
    BuildZ();
    PatternMatch();
}

void Read() {
    freopen("strmatch.in", "r", stdin);
    scanf("%s\n%s", Pattern+1, String+1);
    M = strlen(Pattern+1), N = strlen(String+1);
}

void Print() {
    freopen("strmatch.out", "w", stdout);
    printf("%d\n", MatchPos.size());
    for (int i = 0; i < 1000 && i < MatchPos.size(); ++i)
        printf("%d ", MatchPos[i]);
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}