Pagini recente » Cod sursa (job #1865809) | Cod sursa (job #2624957) | Cod sursa (job #1770019) | Cod sursa (job #368030) | Cod sursa (job #1096800)
#include<fstream>
#include<string>
using namespace std;
int i,n,pref[2000005],sol[1005],nr;
string s1,s2;
void makeprefix(){
n=s1.length()-1;
pref[1]=0; pref[0]=-1;
for (int i=2; i<=n; ++i) {
int aux=pref[i-1];
while (s1[i]!=s1[aux+1]&&aux>=0) aux=pref[aux];
pref[i]=aux+1;
}
}
int main(void) {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
getline(fin,s1); s1=' '+s1;
getline(fin,s2); s2=' '+s2;
makeprefix();
int poz=1;
for (i=1; i<s2.length(); ++i) {
while (s2[i]!=s1[poz]&&poz>0) poz=pref[poz];
if (s2[i]==s1[poz]) ++poz;
if (poz==n+1) {
++nr; poz=pref[n]+1;
if (nr<=1000) sol[nr]=i-1;
}
}
fout<<nr<<"\n";
for (i=1; i<=min(1000,nr); ++i) fout<<sol[i]-n+1<<" ";
return(0);
}