Pagini recente » Cod sursa (job #198501) | Cod sursa (job #870520) | Cod sursa (job #606376) | Cod sursa (job #1704694) | Cod sursa (job #998646)
Cod sursa(job #998646)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 4000005
using namespace std;
string a, b, s;
int Z[nmax];
int L = 0, R = 0, B, 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();
for(int k=1; k<s.size(); k++) {
if(s[k] != s[0]) continue; //n-am treaba pe-aici
if(k >= R) {
i = 0;
j = k;
while(j < s.size() && 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 < s.size() && 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<s.size(); i++)
if(Z[i] >= a.size()) sol++;
g<<sol<<"\n";
sol = min(sol, 1000);
for(int i=a.size(); i<s.size() && sol; i++)
if(Z[i] >= a.size()) g<<i-a.size()<<" ", sol--;
return 0;
}