Pagini recente » Cod sursa (job #1816057) | Cod sursa (job #3189735) | Cod sursa (job #3205696) | Cod sursa (job #483308) | Cod sursa (job #2879576)
#include <fstream>
#include <iostream>
#include <cstring>
#define N 2000005
using namespace std;
char pattern[N], str[N];
int pi[N];
void read() {
ifstream f("strmatch.in");
f >> pattern;
f >> str;
f.close();
}
void buildPi(char s[]) {
int len = 0;
pi[0] = 0;
int i = 1;
int patSize = strlen(s);
while (i < patSize) {
if (s[i] == s[len]) {
len++;
pi[i] = len;
i++;
}
else {
if (len != 0)
len = pi[len - 1];
else {
pi[i] = 0;
i++;
}
}
}
}
void solve() {
ofstream g("strmatch.out");
read();
int sol[N], k;
k = 0;
buildPi(pattern);
int patSize = strlen(pattern) + 1;
pattern[patSize] = NULL;
for(int i = patSize - 1; i > 0; --i) {
pattern[i] = pattern[i - 1];
pi[i] = pi[i - 1];
}
pattern[0] = '0';
int i = 0, j = 0;
while(i < strlen(str)) {
if(pattern[j + 1] == NULL) {
sol[k++] = i - j;
j = pi[j];
}
if(str[i] != pattern[j + 1]) {
i++;
j = pi[j];
}
else {
i++;
j++;
}
}
g << k << "\n";
for(int i = 0; i < k; ++i)
g << sol[i] << " ";
g.close();
}
int main() {
solve();
return 0;
}