Pagini recente » Cod sursa (job #1622279) | Cod sursa (job #324376) | Cod sursa (job #1352673) | Cod sursa (job #639522) | Cod sursa (job #2764651)
#include <iostream>
#include <fstream>
#include <cstring>
#define LMAX 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char s[2 * LMAX + 1 + 1];
int Z[2 * LMAX + 1 + 1];
int main()
{
fin.getline(s, LMAX + 1);
int LGA = strlen(s);
s[ LGA ] = '$';
fin.getline(s + LGA + 1, LMAX + 1);
int lg = strlen(s);
Z[0] = lg;
int left = 0;
int right = 0;
for(int i = 1; i < lg; i++){
if(i > right){
left = i;
right = i;
while(right < lg && s[right] == s[right - left]){
right++;
}
right--;
Z[i] = right - left + 1;
}
else {
int pI = i - left;
if( i - 1 + Z[pI] < right ){
Z[i] = Z[pI];
}
else {
left = i;
while(right < lg && s[right] == s[right - left]){
right++;
}
right--;
Z[i] = right - left + 1;
}
}
}
int nrAparitii = 0;
for(int i = LGA + 1; i < lg; i++){
if(Z[i] == LGA){
nrAparitii++;
}
}
fout << nrAparitii << "\n";
int afis = 0;
for(int i = LGA + 1; i < lg; i++){
if(Z[i] == LGA && afis < 1000){
fout << i - (LGA + 1) << ' ';
afis++;
}
}
return 0;
}