Pagini recente » Cod sursa (job #2384872) | Cod sursa (job #305627) | Cod sursa (job #1228403) | Cod sursa (job #75144) | Cod sursa (job #984019)
Cod sursa(job #984019)
//KMP
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#define REP(i, a, b) for(int i = a; i <= b; ++i)
#define FOR(i, n) REP(i, 1, n)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define read(n) int (n); scanf("%d", &(n))
#define read2(n, m) int (n), (m); scanf("%d %d", &(n), &(m))
#define read3(n, m, k) int (n), (m), (k); scanf("%d %d %d", &(n), &(m), &(k))
#define ll long long
#define x first
#define y second
#define mp make_pair
using namespace std;
int cP, cS, F[2000100], matches[2000100];
char P[2000100], S[2000100];
void failure() {
REP(i, 2, cP) {
int pref = F[i - 1];
while (1) {
if (P[i] == P[pref + 1]) {
F[i] = pref + 1;
break;
}
if (!pref)
break;
pref = F[pref];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(P + 1); gets(S + 1);
cP = strlen(P + 1), cS = strlen(S + 1);
failure();
int i = 1, mat = 0;
while (1) {
if (i == cS + 1)
break;
if (S[i] == P[mat + 1]) {
++i;
++mat;
if (mat == cP)
matches[++matches[0]] = i - cP - 1;
continue;
}
if (mat == 0)
++i;
else
mat = F[mat];
}
printf("%d\n", matches[0]);
chmin(matches[0], 1000);
FOR(i, matches[0])
printf("%d ", matches[i]);
return 0;
}