Pagini recente » Cod sursa (job #1954406) | Cod sursa (job #1612892) | Cod sursa (job #1614824) | Cod sursa (job #1962207) | Cod sursa (job #1610688)
# include <fstream>
# include <cstring>
# define DIM 2000010
using namespace std;
int P[DIM], S[1010];
char A[DIM], B[DIM];
int n, m, i, q, k;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> A+1;
n = strlen(A+1);
fin >> B+1;
m = strlen(B+1);
// preprocesare pentru A: A[i] = lungimea maxima a unui sufix al lui A terminat pepozitia i
// care e in acelasi timp prefix (lungime < i)
q = 0;
P[1] = 0;
for (i=2;i<=n; ++i) {
// calcule P[i]
while (A[i] != A[q+1] && q!=0)
q = P[q];
if (A[i] == A[q+1])
++q;
P[i] = q;
}
q = 0;
for (i=1; i<=m; ++i) {
while (B[i] != A[q+1] && q!=0)
q = P[q];
if (B[i] == A[q+1])
q++;
if (q == n) {
k++;
if (k <= 1000)
S[k] = i-n;
q = P[q];
}
}
fout << k << "\n";
if (k > 1000)
k = 1000;
for (i=1; i<=k; i++)
fout << S[i] << " ";
return 0;
}