Pagini recente » Cod sursa (job #859442) | Cod sursa (job #1835094) | Cod sursa (job #1940350) | Cod sursa (job #1885988) | Cod sursa (job #1592373)
// KMPforMicrosoft.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
#define N 1000
using namespace std;
vector<int> getKmpMachine(const string & str) {
vector<int> kmp(str.size() + 1, 0);
int state = 0;
for (size_t i = 1; i < str.length(); ++i) {
while (state > 0 && str[state] != str[i]) {
state = kmp[state];
}
if (str[state] == str[i])
++state;
kmp[i + 1] = state;
}
return kmp;
}
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
string small, large;
fin >> small;
fin >> large;
vector<int> kmpMachine = getKmpMachine(small);
vector<int> result;
int count = 0;
size_t state = 0;
for (size_t i = 0; i < large.length(); ++i) {
while (state > 0 && large[i] != small[state]) {
state = kmpMachine[state];
}
if (small[state] == large[i])
++state;
if (state == small.length()) {
++count;
state = kmpMachine[state];
if (count <= N) {
result.push_back(i - small.length() + 1);
}
}
}
fout << count << "\n";
for (size_t i = 0; i < result.size(); ++i) {
fout << result[i] << ' ';
}
return 0;
}