Pagini recente » Cod sursa (job #297114) | Cod sursa (job #60673) | Cod sursa (job #431891) | Cod sursa (job #641027) | Cod sursa (job #1074936)
#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];
}
}
out<<r.size()<<"\n";
for(int i=0;i<r.size();i++)
out<<r[i]<<" ";
return 0;
}