Pagini recente » Cod sursa (job #2692647) | Cod sursa (job #2143142) | Cod sursa (job #1958285) | Cod sursa (job #366120) | Cod sursa (job #2596019)
// redo strmatch with KMP(Knuth-Morris-Pratt), but use 0-based indexing for the prefix function (for consistency)
#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;
/*
* pi - the prefix function: [0, N-1] -> [-1, N-2]
the argument - is the current position in string A.
the value is the corresponding position in A or -1 if no prefix of A is a suffix ending in current position.
for all n, pi[n] < n.
*/
int pi[Nmax];
int N, M;
string A,B;
void build_prefix() {
pi[0] = -1;
int k = -1;
// k -> the current accepted state; the position of the current largest prefix (just before starting the current iteration)
for(uint i = 1; i < A.size(); i++) {
while(k > -1 && A[i] != A[k+1]) { k = pi[k]; }
if (A[i] == A[k+1]) { k++; }
pi[i] = k;
}
}
int main(void) {
fin >> A >> B;
N = A.size();
M = B.size();
if (N > M) {
fout << "0\n";
return 0;
}
build_prefix();
int k = -1;
int count = 0;
vi res;
rep(i, M) {
while(k > -1 && B[i] != A[k+1]) { k = pi[k]; }
if (B[i] == A[k+1]) { k++; }
if (k == N-1) {
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;
}