Pagini recente » Cod sursa (job #686526) | Cod sursa (job #2311479) | Clasament FMI No Stress 4 | Clasament FMI No Stress 3 | Cod sursa (job #998378)
Cod sursa(job #998378)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 4000005
using namespace std;
string a, b, s;
int Z[nmax];
int L = 0, R = 1, k, kprim, i, j, cnt;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f, a);
getline(f, b);
s = a + b;
Z[0] = s.size();
for(k = 1; k < s.size(); k++) {
if(s[k] != s[0]) { Z[k] = 0; continue; }
if(k > R) {
i = 0;
j = k;
while(j < s.size() && s[i] == s[j]) i++, j++;
L = k;
R = j-1;
Z[k] = R - L + 1;
}
else {
kprim = k - L;
if(k==10)
cout<<s[k]<<": k = "<<k<<" si k' = "<<kprim<<"\n";
if(Z[kprim] < R - k + 1) {
Z[k] = Z[kprim];
}
else {
i = kprim + Z[kprim] - 1;
j = R;
while(j < s.size() && s[i] == s[j]) i++, j++;
L = k;
R = j;
Z[k] = Z[kprim] + R - L + 1;
}
}
}
Z[0] = 0;
//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=0; i<s.size(); i++)
if(Z[i] >= a.size() && i >= a.size()) cnt++;
g<<cnt<<"\n";
cnt = min(cnt, 1000);
for(int i=0; i<s.size(); i++)
if(cnt && Z[i] >= a.size() && i >= a.size())
g<<i-a.size()<<" ", cnt--;
return 0;
}