Pagini recente » Istoria paginii runda/simulareoji_2008_11-12_vineri | Cod sursa (job #2311753) | Cod sursa (job #2778057) | Cod sursa (job #1084362) | Cod sursa (job #1096822)
#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=0;
for (i=1; i<s2.length(); ++i) {
while (s2[i]!=s1[poz+1]&&poz>0) poz=pref[poz];
if (s2[i]==s1[poz+1]) ++poz;
if (poz==n) {
++nr; poz=pref[n];
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);
}