Pagini recente » Cod sursa (job #1278355) | Cod sursa (job #3214949) | Cod sursa (job #1312145) | Cod sursa (job #750688) | Cod sursa (job #1791899)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define NMAX 2000005
char pattern[NMAX], text[NMAX];
int pTable[NMAX];
void searchPattern(char *pattern, char *text) {
int len = 0, i = 0, n = strlen(pattern) - 1, m = strlen(text) - 1;
vector <int> sol;
while (i <= m) {
if (text[i] == pattern[len]) {
len++;
i++;
}
if (len == n + 1) {
if (sol.size() < 1000) sol.push_back(i - len);
len = pTable[len - 1];
}
else if (i <= m && text[i] != pattern[len]) {
if (len != 0) {
len = pTable[len - 1];
}
else i++;
}
}
printf("%d\n", sol.size());
vector <int> ::iterator it;
for (it = sol.begin(); it != sol.end(); it++) {
printf("%d ", *it);
}
}
void buildPartialTable(char *s) {
int len = 0, i = 1, n = strlen(s);
pTable[0] = 0;
while (i < n) {
if (s[i] == s[len]) {
len++;
pTable[i] = len;
i++;
}
else if (len != 0) {
len = pTable[len - 1];
}
else i++;
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(pattern);
gets(text);
buildPartialTable( pattern );
searchPattern( pattern, text);
}