Pagini recente » Cod sursa (job #1382679) | Cod sursa (job #1343630) | Cod sursa (job #2429706) | Cod sursa (job #1332254) | Cod sursa (job #2458575)
#include <bits/stdc++.h>
#define N 2000 + 5
using namespace std;
vector<int> v;
ofstream fout("strmatch.out");
char A[N], B[N];
int pi[N];
void calc_pi() {
int i = 1, j = 1;
pi[1] = 0;
while(A[++j])
if(A[i] == A[j]) pi[j] = i, ++i;
else if(i != 1) i = 1, --j;
}
void calc_kmp() {
int n = 0, i = 1, j = 0;
do {
if(B[i] == A[j+1]) {
++j;
if(!A[j+1]) {
++n;
if(v.size() < 1000) v.push_back(i - j);
j = pi[j];
}
} else if(j) {
do {
j = pi[j];
} while(B[i] != A[j+1] && j);
--i;
}
} while(B[++i]);
(fout << n).put('\n');
for(int x : v)
(fout << x).put(' ');
}
int main() {
ifstream fin("strmatch.in");
fin >> (A+1) >> (B+1);
calc_pi(); calc_kmp();
//for(int i = 1; A[i]; ++i)
// cout << A[i] << ": " << pi[i] << endl;
}