Pagini recente » Cod sursa (job #752567) | Cod sursa (job #1707186) | Cod sursa (job #592534) | Cod sursa (job #1667465) | Cod sursa (job #998652)
Cod sursa(job #998652)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 4000005
using namespace std;
vector <int> v;
string a, b, s;
int Z[nmax];
int L = 0, R = 0, B, n, k, kprim, i, j, sol = 0;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f, a);
getline(f, b);
s = a + b;
Z[0] = s.size();
n = s.size();
for(int k=1; k<n; k++) {
if(s[k] != s[0]) continue; //n-am treaba pe-aici
if(k >= R) {
i = 0;
j = k;
while(j < n && s[i] == s[j]) Z[k]++, i++, j++;
L = k;
R = k + Z[k] - 1;
}
else {
kprim = k - L;
B = R - k + 1;
if(Z[kprim] <= B) Z[k] = Z[kprim];
else {
Z[k] = B;
i = R - L + 1;
j = R + 1;
while(j < n && s[i] == s[j]) Z[k]++, i++, j++;
L = k;
R = k + Z[k] - 1;
}
}
//cout<<"Dupa k = "<<k<<" (litera <"<<s[k]<<">), L = "<<L<<" si R = "<<R<<"\n";
}
//cout<<"\n ";
//for(int i=0; i<s.size(); i++) cout<<s[i]<<" "; cout<<"\n";
//for(int i=0; i<s.size(); i++) cout<<Z[i]<<" "; cout<<"\n";
for(int i=a.size(); i<n; i++)
if(Z[i] >= a.size()) sol++, v.push_back(i-a.size());
g<<sol<<"\n";
for(int i=0; i<min(int(v.size()), 999); i++) g<<v[i]<<" ";
return 0;
}