Pagini recente » Cod sursa (job #2212037) | Cod sursa (job #505499) | Cod sursa (job #1084158) | Borderou de evaluare (job #1567207) | Cod sursa (job #2418449)
#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 = 2000666;
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) {
int N = A.length();
pi[1] = 0;
int k = 0;
for (int n = 1; n < N; n++) {
while(k > 0 && A[n] != A[k]) {
k = pi[k];
}
if (A[n] == A[k]) {
k++;
}
pi[n+1] = k;
}
}
vi answer;
int main(void) {
string A, B;
fin >> A >> B;
int N = A.length();
int M = B.length();
build_pi(pi, A);
int count = 0;
int k = 0;
for(int n = 0; n < M; n++) {
while(k > 0 && B[n] != A[k]) {
k = pi[k];
}
if (B[n] == A[k]) {
k++;
}
if (k == N) {
k = pi[N];
if (count < 1000) {
answer.push_back(n - N + 1);
}
count++;
}
}
fout << count << "\n";
for(int pos: answer) {
fout << pos << ' ';
}
fout << endl;
return 0;
}