Pagini recente » Cod sursa (job #1452883) | Cod sursa (job #1415805) | Cod sursa (job #1045963) | Cod sursa (job #1273794) | Cod sursa (job #2305004)
#include <bits/stdc++.h>
#define DIM 2000005
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int n, m, i, L, k;
int p[DIM], sol[1005];
char a[DIM], b[DIM];
int main(){
//A[i] = lungimea maxima a unui sufix terminat pe pozitia i care e in acelasi timp prefix (lungime < i).
fin >> a + 1, n = strlen(a + 1);
fin >> b + 1, m = strlen(b + 1);
L = 0, p[1] = 0;
for (i=2; i<=n; i++){
while (a[i] != a[L+1] && L != 0){
L = p[L];
}
if (a[i] == a[L+1]){
L++;
}
p[i] = L;
}
L = 0;
for (i=1; i<=m; i++){
while (b[i] != a[L+1] && L != 0){
L = p[L];
}
if (b[i] == a[L+1]){
L++;
}
if (L == n){ /// daca gasesc potrivire
k++;
if (k <= 1000){
sol[k] = i - n;
}
L = p[L];
}
}
fout << k << "\n";
if (k > 1000)
k = 1000;
for (i=1; i<=k; i++){
fout << sol[i] << " ";
}
return 0;
}