Pagini recente » Cod sursa (job #857742) | Cod sursa (job #2333985) | Cod sursa (job #3205183) | Cod sursa (job #1321675) | Cod sursa (job #1478771)
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
int n, alen;
int zFunction[4000002];
int leftLimit, rightLimit;
int main(void){
in >> a;
in >> b;
alen = a.length();
a += "#"+b;
n =a.length();
leftLimit = 0;rightLimit = 0;
for (int i=1;i<n;i++){
if (i<=rightLimit) zFunction[i] = min(zFunction[i-leftLimit], rightLimit-i+1);
while(i+zFunction[i]<n && a[i+zFunction[i]]==a[zFunction[i]]) zFunction[i]++;
if(i+zFunction[i]-1>rightLimit){
leftLimit = i;
rightLimit = i+zFunction[i]-1;
}
}
int count=0;
for (int i=0;i<n;i++){
if (zFunction[i]==alen)count++;
}
out << count << "\n";
count = 0;
for (int i=0;i<n && count<1000;i++)
if (zFunction[i]==alen){
out << i-alen-1 << " ";
count++;
}
out << "\n";
return 0;
}