Pagini recente » Cod sursa (job #132307) | Cod sursa (job #442336) | Cod sursa (job #2046971) | Cod sursa (job #863363) | Cod sursa (job #2417895)
// String Match cu KMP
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
// const int INF = 0x3f3f3f3f;
const int Nmax = 2000666;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int N, M;
// A indexat de la 1.
// fie A_i,A_x prefixele stringului A de lungime i, respectiv x.
// pi[x] este cel mai mare i < x, astfel incat A_i, este sufix pentru A_x.
// pi[x] este 0 daca nici un prefix de-a lui A nu-i sufix pentru A_x.
// pi: {1..N} -> {0..N-1}
// pi[0] nu este definit (sau 0)
int pi[Nmax];
vector<int> result;
int main(void) {
string A, B;
fin >> A >> B;
N = A.length();
M = B.length();
// build the pi function
int k;
pi[1] = 0;
for(int n = 2; n <= N; n++) {
k = pi[n-1];
// A_k is sufix for A_(n-1)
while(k > 0 && A[n-1] != A[k]) {
k = pi[k];
}
if (A[k] == A[n-1]) {
k++;
}
pi[n] = k;
}
// compute all appearances;
int count = 0;
k = 0;
for(int i = 0; i < M; i++) {
while(k > 0 && B[i] != A[k]) {
k = pi[k];
}
if (B[i] == A[k]) {
k++;
}
if (k == N) {
count++;
if (count <= 1000) {
result.push_back(i - N + 1);
}
k = pi[N];
}
}
fout << count << "\n";
for(int pos: result) {
fout << pos << ' ';
}
fout << endl;
return 0;
}