Pagini recente » Cod sursa (job #2608270) | Cod sursa (job #923685) | Cod sursa (job #610341) | Cod sursa (job #3221983) | Cod sursa (job #1074937)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
string s1,s2;
vector<int> p;
int n,m;
void prefix()
{
int k;
k=0;
p[1]=0;
for(int i=2;i<=n;i++)
{
while(k && s1[k+1]!=s1[i])
k=p[k];
if(s1[k+1]==s1[i])
k++;
p[i]=k;
}
}
int main()
{
int k=0;
vector <int> r;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in,s1);
s1="*"+s1;
getline(in,s2);
s2="%"+s2;
n=s1.size()-1;
m=s2.size()-1;
p.reserve(n);
prefix();
for(int i=1;i<=m;i++)
{
while(k && s1[k+1]!=s2[i])
k=p[k];
if(s1[k+1]==s2[i])
k++;
if(k==n)
{
r.push_back(i-n);
k=p[k];
}
if(r.size()==1000)
break;
}
out<<r.size()<<"\n";
for(unsigned int i=0;i<r.size();i++)
out<<r[i]<<" ";
return 0;
}