Pagini recente » Cod sursa (job #384598) | Cod sursa (job #184849) | Cod sursa (job #495330) | Cod sursa (job #2230746) | Cod sursa (job #1213331)
#include <fstream>
#include <string>
#define NMAX 2000001
#define RMAX 1000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int t[NMAX], pos[NMAX], nr;
int min(int a, int b) {
if (a < b)
return a;
return b;
}
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 - 1 < s.length(); ++i) {
if (w[m] == s[i]) {
m++;
if (m == n) {
pos[nr] = i - m + 1;
nr++;
m = t[m-1];
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 < min(nr, RMAX); ++i) {
g << pos[i] << " ";
}
g << "\n";
return 0;
}