Pagini recente » Cod sursa (job #1317165) | Cod sursa (job #1128223) | Cod sursa (job #1565354) | Cod sursa (job #2614446) | Cod sursa (job #1243604)
//
// 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("grader_test4.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] != A[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 < NMAX) {
Sol[t] = i - n + 1;
}
++t;
}
}
}
void print () {
out << t << "\n";
if (t > NMAX) {
t = NMAX;
}
for (int i = 0; i < t; ++i) {
out << Sol[i] << " ";
}
}