Pagini recente » Cod sursa (job #1949435) | Cod sursa (job #188277) | Cod sursa (job #162162) | Cod sursa (job #544494) | Cod sursa (job #1074954)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 2000005
string s1,s2;
int p[nmax];
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;
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];
}
}
k=r.size();
out<<k<<"\n";
for(unsigned int i=0;i<min(k,1000);i++)
out<<r[i]<<" ";
return 0;
}