Pagini recente » Cod sursa (job #2516666) | Cod sursa (job #2633111) | Cod sursa (job #593508) | Cod sursa (job #3264750) | Cod sursa (job #1834986)
#include<iostream>
#include<string>
#include<cstdlib>
#include<fstream>
using namespace std;
int values[1001];
int *getPrefixes(string w, int n) {
int *prefix = (int *) calloc (n, sizeof(int));
int i = 1;
int j = 0;
while (i < n) {
if (w[i] == w[j]) {
prefix[i] = j + 1;
i++;
j++;
} else if (j == 0) {
i++;
} else {
j = prefix[j - 1];
}
}
return prefix;
}
int getIndexes(string w, string s, int n, int k, int prefix[]) {
int m = 0;
int i = 0;
int count = 0;
while (m < k - n + 1) {
if (i == n) {
//printf("%d ", m);
//cout << s.substr(m, i) << '\n';
values[count++] = m;
m = m + i - prefix[i - 1];
i = prefix[i - 1];
}
if (s[m + i] == w[i]) {
i++;
} else if (i == 0 ){
m = m + 1;
} else {
m = m + i - prefix[i];
i = prefix[i - 1];
}
}
return count;
}
int main() {
int n;
int k;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
string w;
string s;
getline(fi, w);
getline(fi, s);
n = w.size();
k = s.size();
int* prefix = getPrefixes(w, n);
/*
for (int i = 0; i < n; i++) {
cout << prefix[i] << ' ';
}
cout << '\n'; */
int count = getIndexes(w, s, n, k, prefix);
fo << count << '\n';
if (count > 1000)
count = 1000;
for (int i = 0; i < count; i++) {
fo << values[i] << ' ';
}
fi.close();
fo.close();
return 0;
}