Pagini recente » Cod sursa (job #1181004) | Cod sursa (job #2063200) | Cod sursa (job #1428038) | Cod sursa (job #1800224) | Cod sursa (job #2595897)
// redo strmatch using KMP (Knuth-Morris-Pratt)
#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;
typedef vector<int> vi;
const int INF = 0x3f3f3f3f;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int Nmax = 2000666;
string A, B;
/*
* pi: prefix function: [1,N] -> [0,N-1]
* both the argument and the value for pi are the string length, not the string position.
* pi[n] < n
*/
int pi[Nmax];
// Todo: pass A and pi as arguments (by reference) to build_prefix()
void build_prefix() {
rep(i, A.size()) {
// we want to determine pi[i+1] (prefix for the substring that ends in A[i])
// we know pi[i] by induction
int k = pi[i]; // yhis means that A[i-1] == A[k-1];
while(k > 0 && A[i] != A[k]) {
k = pi[k];
}
if (i == 0 || A[i] != A[k]) {
pi[i+1] = 0;
} else {
pi[i+1] = k+1;
}
}
}
int main(void) {
fin >> A >> B;
int N = A.size(), M = B.size();
if (N > M) {
fout << "0\n";
return 0;
}
build_prefix();
int count = 0, k = 0;
vi res;
rep(i, M) {
while(k > 0 && B[i] != A[k]) {
k = pi[k];
}
if (B[i] == A[k]) {
k++;
}
if (k == N) {
count++;
if (count <= 1000) { res.push_back(i-(N-1));}
k = pi[k];
}
}
fout << count << '\n';
for(auto pos: res) {
fout << pos << ' ';
}
fout << endl;
return 0;
}