Pagini recente » Cod sursa (job #2486949) | Cod sursa (job #708047) | Cod sursa (job #2529596) | Cod sursa (job #1050899) | Cod sursa (job #829014)
Cod sursa(job #829014)
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
#define N_MAX 2000010
int SOL;
char S[N_MAX], S2[N_MAX];
vector<int> strmatch(char *s, char *p) { //s string to be matched
vector<int> solution;
int n = strlen(s), m = strlen(p);
int pi[n];
memset(pi, 0, sizeof(pi));
int k = 0;
pi[0] = 0;
for(int i = 1; i < n; i++) {
while(k > 0 && s[k] != s[i]) {
k = pi[k-1];
}
if(s[k] == s[i]) {
k++;
}
pi[i] = k;
}
k = 0;
for(int i = 0; i < m; i++) {
while(k > 0 && s[k] != p[i]) {
k = pi[k-1];
}
if(s[k] == p[i]) {
k++;
}
if(k == n) {
SOL++;
if( solution.size() < 1000)
solution.push_back(i-k+1);
k = pi[k-1];
}
}
return solution;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(S, N_MAX, stdin);
fgets(S2, N_MAX, stdin);
int n = strlen(S);
if(S[n-1] == '\n') S[n-1] = 0;
n = strlen(S2);
if(S2[n-1] == '\n') S2[n-1] = 0;
vector <int> sol = strmatch(S, S2);
printf("%d\n", SOL);
for(int i = 0; i < sol.size(); i++) {
printf("%d ", sol[i]);
}
return 0;
}