Pagini recente » Cod sursa (job #389937) | Cod sursa (job #713063) | Cod sursa (job #1293919) | Rating Stangaciu Sofian (Straton) | Cod sursa (job #1096856)
#include<fstream>
#include<string>
using namespace std;
int i,n,m,z[4000005],sol[1005],nr,l,r;
string s, s1;
int main(void) {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin,s); s=' '+s;
m=s.length()-1;
getline(fin,s1);
s+='$'+s1;
n=s.length();
l=r=0;
for (i=2; i<n; ++i) {
if (i>r) {
int p1=1,p2=i,lung=0;
while (s[p1]==s[p2]) { ++p1; ++p2; ++lung; }
--p1; --p2;
z[i]=lung;
if (lung>0) { l=i; r=p2; }
}
else {
int poz=i-l+1, dep=r-i+1;
if (z[poz]<dep) z[i]=z[poz];
else {
int p1=dep+1, p2=r+1, lung=dep;
while (s[p1]==s[p2]) { ++p1; ++p2; ++lung; }
--p1; --p2;
z[i]=lung;
l=i;
r=p2;
}
}
if (z[i]==m) {
++nr;
if (nr<=1000) sol[nr]=i-m-2;
}
}
fout<<nr<<"\n";
for (i=1; i<=min(nr,1000); ++i) fout<<sol[i]<<" ";
return(0);
}