Pagini recente » Cod sursa (job #2280310) | Cod sursa (job #2141231) | Cod sursa (job #1690465) | Cod sursa (job #1856293) | Cod sursa (job #1701751)
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <string>
#include <limits>
#include <vector>
#include <bitset>
#include <utility>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define MOD 10001 // daca e nevoie de mod
#define oo 2000000000
#define ooLL (1LL<<60)
#define LSB(x) (x&(-x)) // least significat bit of
#define eps 0.00001
typedef long long ull;
typedef long double ld;
std::vector<int> compute_pattern_kmp(const std::string& pattern)
{
std::vector<int> pp(pattern.size(), 0);
uint j = 0;
for (uint i = 1; i <= pattern.size(); ++i)
{
while(0 != j && pattern[i] != pattern[j]) {
j = pp[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
pp[i] = j;
}
return pp;
}
std::vector<int> positions_matched_kmp(const std::string& pattern, const std::string& text)
{
std::vector<int> pos;
uint j = 0;
const std::vector<int>& pp = compute_pattern_kmp(pattern);
for (uint i = 0; i < text.size(); ++i)
{
while(0 != j && pattern[j] != text[i]) {
j = pp[j - 1];
}
if (pattern[j] == text[i]) {
j++;
}
if (j == pattern.size()) {
j = pp[pattern.size() - 1];
pos.push_back(i - pattern.size() + 1);
}
}
return pos;
}
int main()
{
std::ifstream cin("strmatch.in");
std::ofstream cout("strmatch.out");
size_t N = 1000;
std::string pattern;
std::string text;
cin >> pattern >> text;
std::vector<int> match_positions = positions_matched_kmp(pattern, text);
cout << match_positions.size() << "\n";
for (size_t i = 0; i < std::min(match_positions.size() , N); ++i)
cout << match_positions[i] << " ";
cin.close();
cout.close();
return 0;
}