Pagini recente » Cod sursa (job #61693) | Cod sursa (job #1941770) | Cod sursa (job #510258) | Cod sursa (job #2588913) | Cod sursa (job #2675072)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void buildLPS(vector<int> &lps, string a){
lps.reserve(a.length());
for (int i = 0; i < a.length(); ++i) {
lps.push_back(0);
}
for (int i = 1, j = 0; i < a.length(); ++i) {
if(a[i] == a[j]) lps[i] = ++j;
else if(j) j = lps[j - 1], --i;
else lps[i] = 0;
}
}
void kmp(vector<int> &matches, vector<int> lps, string a, string b){
for (int i = 0, j = 0; i < b.length();) {
if(a[j] == b[i]){
++i, ++j;
if(j == a.length()) matches.push_back(i - j), j = lps[j - 1];
}
else if(i < b.length() && a[j] != b[i]){
if(j) j = lps[j - 1];
else ++i;
}
if(matches.size() >= 1000) return;
}
}
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
f>>a>>b;
vector<int> matches;
vector<int> lps;
buildLPS(lps, a);
kmp(matches, lps, a, b);
int l = matches.size();
if(1000 < matches.size())
l = 1000;
g<<l<<'\n';
for (int i = 0; i < l; ++i) {
g<<matches[i]<<' ';
}
return 0;
}