Pagini recente » Cod sursa (job #2594332) | Cod sursa (job #2398290) | Cod sursa (job #913453) | Cod sursa (job #267108) | Cod sursa (job #2370644)
#include <fstream>
#include <cstring>
using namespace std;
ifstream inf("strmatch.in");
ofstream outf("strmatch.out");
int lps[2000000];
char s[2000005];
char pattern[2000005];
int result[1000];
void LPS(char *pat, int* lps) {
int len = 0, i = 1;
lps[0] = 0;
int n = strlen(pat);
while(i < n) {
if(pat[len] == pat[i]) {
lps[i] = ++len;
i++;
}
else {
if(len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
int patsearch(char *pat, char *s) {
LPS(pat, lps);
int n = strlen(s);
int m = strlen(pat);
int i = 0, j = 0, rez = 0;
while(i < n) {
if(s[i] == pat[j]) {
i++;
j++;
}
else {
if(j != 0) {
j = lps[j - 1];
}
else {
i++;
}
}
if(j == m) {
if(rez < 1000) {
result[rez] = i - m;
}
rez++;
j = lps[j - 1];
}
}
return rez;
}
int main() {
inf >> pattern >> s;
int rez = patsearch(pattern, s);
outf << rez << '\n';
rez = min(rez, 1000);
for(int i = 0; i < rez; i++) {
outf << result[i] << ' ';
}
return 0;
}