Pagini recente » Cod sursa (job #3168294) | Cod sursa (job #2762287) | Cod sursa (job #2587200) | Cod sursa (job #327189) | Cod sursa (job #2418348)
#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];
vi answer;
int main(void) {
string A, B;
fin >> A >> B;
int N = A.length();
int M = B.length();
A = "_" + A;
B = "_" + B;
// build pi
int k;
pi[0] = pi[1] = 0;
for(int i = 2; i <= N; i++) {
k = pi[i-1];
while(k > 0 && A[i] != A[k+1]) {
k = pi[k];
}
if (A[i] == A[k+1]) {
k++;
}
pi[i] = k;
}
int count = 0;
// compute matches
k = 0;
for(int i = 1; i <= M; i++) {
while(k > 0 && B[i] != A[k+1]) {
k = pi[k];
}
if (B[i] == A[k+1]) {
k++;
}
if (k == N) {
if (count < 1000) {
answer.push_back(i - N + 1 - 1); // answers should be 0-indexed.
}
count++;
k = pi[k];
}
}
fout << count << '\n';
if (count > 0) {
for(int i: answer)
fout << i << ' ';
fout << endl;
}
return 0;
}