Pagini recente » Cod sursa (job #1628647) | Cod sursa (job #689974) | Cod sursa (job #1075624) | Cod sursa (job #2328092) | Cod sursa (job #2418446)
#include <stdio.h>
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int Nmax = 1333;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int pi[Nmax];
// builds the KMP prefix function for the string A.
void build_pi(int* const pi, const string &A) {
pi[1] = 0;
int k = 0;
for (int n = 2; n <= A.length(); n++) {
while(k > 0 && A[n-1] != A[k]) {
k = pi[k];
}
if (A[n-1] == A[k]) { k++; }
pi[n] = k;
}
}
vi answer;
int main(void) {
string A, B;
fin >> A >> B;
build_pi(pi, A);
int count = 0;
int k = 0;
for(int n = 0; n < B.length(); n++) {
while(k > 0 && B[n] != A[k]) {
k = pi[k];
}
if (B[n] == A[k]) { k++; }
if (k == A.length()) {
k = pi[k];
if (count < 1000) {
answer.push_back(n - A.length() + 1);
}
count++;
}
}
fout << count << "\n";
for(int pos: answer) {
fout << pos << ' ';
}
fout << endl;
return 0;
}