Pagini recente » Cod sursa (job #2684514) | Cod sursa (job #1799126) | Cod sursa (job #1947580) | Cod sursa (job #1207114) | Cod sursa (job #1478751)
#include <fstream>
#include <string>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string a,b;
int n, alen;
int zFunction[4000000];
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 && a[i]==a[0]){
leftLimit = i;
for (rightLimit = leftLimit; rightLimit+1<n, a[rightLimit+1]==a[rightLimit-leftLimit+1];rightLimit++);
zFunction[i]=rightLimit-leftLimit+1;
}else if(i<=rightLimit){
zFunction[i] = zFunction[rightLimit-i];
if (rightLimit-i<=zFunction[i]){
leftLimit = i;
rightLimit = i+zFunction[i]-1;
for (;rightLimit+1<n, a[rightLimit+1]==a[rightLimit-leftLimit+1];rightLimit++);
zFunction[i]=rightLimit-leftLimit+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++;
}
return 0;
}