Pagini recente » Cod sursa (job #2396102) | Cod sursa (job #1139409) | Cod sursa (job #2649389) | Cod sursa (job #1751547) | Cod sursa (job #1719737)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int main()
{
string p,s;
f>>p>>s;
int nr=0,cnt=0;
vector<int> matches(1000);
int n=s.size(),m=p.size();
vector<int> pref(m);
pref[0]=0;
int q=0;
for(int i=1;i<m;i++)
{
while(q!=0 && p[i]!=p[q]) q=pref[q-1];
if(p[i]==p[q]) ++q;
pref[i]=q;
}
q=0;
for(int i=0;i<n;i++){
while(q!=0 && s[i]!=p[q]) q=pref[q-1];
if(s[i]==p[q]) q++;
if(q==m)
{
nr++;
if(cnt<1000) matches[cnt++]=i-m+1;
q=pref[q-1];
}
}
g<<nr<<'\n';
for(int i=0;i<cnt;i++) g<<matches[i]<<' ';
}