Pagini recente » Cod sursa (job #809175) | Cod sursa (job #1286109) | Cod sursa (job #1033557) | Cod sursa (job #2185303) | Cod sursa (job #2910003)
#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[0] = 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] == a[i+1]){
Lmax++;
}
/// actualizam lungimea maxima a sufixului de pe poz i
pref[i] = Lmax;
}
/// facem acelasi lucru pentru b
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){
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<=ans;i++){
cout << sol[i] << ' ';
}
}