Cod sursa(job #1243595)

Utilizator yellowstarTraian Mihai yellowstar Data 16 octombrie 2014 01:57:49
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
//
//  main.cpp
//  strmatch
//
//  Created by Hai Tran Bach on 10/15/14.
//  Copyright (c) 2014 Hai Tran Bach. All rights reserved.
//

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

#define NMAX 1000

string A, B;
int n, m, t, Sol[NMAX];

vector<int> Pi;

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

void read();

void prefix();

void kmp();

void print();

int main() {
    
    read();
    prefix();
    kmp();
    print();
    
    return 0;
}

void read() {
    
    in >> A >> B;
    n = A.length();
    m = B.length();
}

void prefix() {
   
    int k = 0;
    Pi.push_back(0);
    for (int i = 1; i < n; ++i) {
        while (k > 0 && A[k] != B[i]) {
            k = Pi[k-1];
        }
        if (A[k] == A[i]) {
            ++k;
        }
        Pi.push_back(k);
    }
    
}

void kmp () {
    
    int q = 0;
    
    for (int i = 0; i < m; ++i) {
        while (q > 0 && A[q] != B[i]) {
            q = Pi[q-1];
        }
        if (A[q] == B[i]) {
            q = q + 1;
        }
        if (q == n) {
            if (t < 1000) {
                Sol[t] = i - n + 1;
            }
            ++t;
        }
    }
} 

void print () {
    
    out << t << "\n";
    if (t > 1000) {
        t = 1000;
    }
    for (int i = 0; i < t; ++i) {
        out << Sol[i] << " ";
    }
}