Pagini recente » Cod sursa (job #1523512) | Cod sursa (job #3290064) | Cod sursa (job #771679) | Cod sursa (job #1067609) | Cod sursa (job #1213312)
#include <fstream>
#include <string>
#define NMAX 2000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int t[NMAX], pos[NMAX], nr;
void build_table(string s, int n) {
int m = 0;
t[0] = -1;
for (int i = 1; i < n; ++i) {
t[i] = m;
if (s[i] == s[m]) {
m++;
}
else {
m = 0;
}
}
}
void find_occurences(string w, string s) {
int m = 0, n = w.length();
nr = 0;
for (int i = 0; i + n - m < s.length(); ++i) {
if (w[m] == s[i]) {
m++;
if (m == n) {
pos[nr++] = i - m + 1;
m = t[m];
if (m != -1) {
i--;
}
else {
m = 0;
}
}
}
else {
m = t[m];
if (m != -1) {
i--;
}
else {
m = 0;
}
}
}
}
int main() {
string a, b;
f >> a >> b;
build_table(a, a.length());
/*/
for (int i = 0; i < a.length(); ++i) {
g << t[i] << " ";
}
//*/
find_occurences(a, b);
g << nr << "\n";
for (int i = 0; i < nr; ++i) {
g << pos[i] << " ";
}
return 0;
}