Pagini recente » Cod sursa (job #1914472) | Cod sursa (job #1407160) | Cod sursa (job #164654) | Cod sursa (job #2739130) | Cod sursa (job #2911081)
#include <bits/stdc++.h>
using namespace std;
char a[2000001], b[2000001];
int pref[2000002];
int sol[2000002];
int main(void){
ofstream cout("strmatch.out");
ifstream cin("strmatch.in");
cin >> a+1 >> b+1;
int n,m, Lmax = 0, ans = 0;
n = strlen(a+1);
m = strlen(b+1);
pref[1] = 0; /// primul prefix nu este si sufix
for(int i = 2;i<=n;i++){
/// cautam "sub sufixe" (sufixe care se afla in sufixul de lungime maxima si ne uitam daca il putem "mari"
while(Lmax != 0 && a[i] != a[Lmax+1]){
Lmax = pref[Lmax];
}
/// Daca putem creste sufixul vom incrementa Lungimea maxima
if(a[Lmax+1] == a[i]){
Lmax++;
}
/// actualizam lungimea maxima a sufixului de pe poz i
pref[i] = Lmax;
}
Lmax = 0;
for(int i = 1;i<=m;i++){
while(Lmax != 0 && b[i] != a[Lmax+1]){
Lmax = pref[Lmax];
}
if(b[i] == a[Lmax+1]){
Lmax++;
}
/// vedem daca exista un sufix care este prefix din a cu lungimea lui a
if(Lmax == n){
ans++; /// crestem numarul de aparitii a lui A in B
if(ans <= 1000)
sol[ans] = i - n;
Lmax = pref[Lmax]; /// ne uitam inca o data in "sub sufix"-ul sufixului in care am gasit cuvantul pentru a vedea daca marind sufixul gasim un sufix de lungimea lui a
}
}
cout << ans << endl;
for(int i = 1;i<=min(ans, 1000);i++){
cout << sol[i] << ' ';
}
}