Pagini recente » Cod sursa (job #1125637) | Cod sursa (job #2964265) | Cod sursa (job #2393385) | Cod sursa (job #176429) | Cod sursa (job #964074)
Cod sursa(job #964074)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
vector<int>qq;
int uu[2000013], nr;
string pp, ss;
void pat(){
int k,l = pp.length();
uu[0]=k=-1;
for(int i=1;i<l;i++)
{
while(k>-1 && pp[i] != pp[k+1])k = uu[k];
if(pp[i]==pp[k+1])k++;
uu[i]=k;
}
//for(int i=0;i<l;i++) cout << uu[i] << " ";
//cout << endl;
}
void mat(){
int k, l1 = pp.length(), l2 = ss.length();
k=-1;
for(int i=0;i<l2;i++)
{
while(k>-1 && ss[i] != pp[k+1])k=uu[k];
if(ss[i] == pp[k+1])k++;
if(k==l1-1)
{
if(nr<1000) qq.push_back(i-l1+1);
nr++;
k=uu[k];
}
}
g << nr << endl;
l1 = qq.size();
for(int i=0;i<l1;i++)
g << qq[i] << " ";
}
int main(){
f >> pp >> ss;
pat();
mat();
return 0;
}