Pagini recente » Cod sursa (job #1530552) | Cod sursa (job #458639) | Cod sursa (job #2036363) | Cod sursa (job #1113899) | Cod sursa (job #2717252)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pattern, text;
vector <int> ans;
int pos;
int lps[2000005];
int main() {
f >> pattern;
f >> text;
for (int i = 1; i < pattern.size(); ++i) {
if(pattern[pos] == pattern[i]) {
lps[i] = ++pos;
}
else if(pos == 0) {
lps[pos] = 0;
}
else {
--i;
pos = lps[pos - 1];
}
}
pos = 0;
int i = 0;
while (i < text.size()) {
if (text[i] == pattern[pos]) {
++i;
++pos;
}
else if(pos == 0)
++i;
else pos = lps[pos - 1];
if(pos == pattern.size()) {
// it's a match!!!
ans.push_back(i - pattern.size());
if(ans.size() == 1000)
break;
pos = lps[pos - 1];
}
}
g << ans.size() << '\n';
for (auto it:ans)
g << it << ' ';
return 0;
}