Cod sursa(job #2337147)
Utilizator | Data | 5 februarie 2019 22:21:23 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.87 kb |
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=1000+7;
struct presuff
{
vector<int>kek;
vector<int>poz;
string pat,s;
int i;
int j;
int n;
int m;
void build(string _pat)
{
pat=_pat;
m=pat.size();
kek.resize(m,0);
int p=1,cur=0;
while(p<m)
{
if(pat[p]==pat[cur])
{
cur++;
kek[p]=cur;
p++;
}
else
{
if(cur==0)
{
p++;
}
else
{
cur=kek[cur-1];
}
}
}
}
void next_step()
{
while(1)
{
if(s[i]==pat[j])
{
i++;
j++;
if(j==m)
{
poz.push_back(i-m);
j=kek[j-1];
}
break;
}
if(s[i]!=pat[j])
{
if(j==0)
{
i++;
break;
}
else
{
j=kek[j-1];
}
}
}
}
void kmp(string _s)
{
poz.clear();
s=_s;
int n=s.size();
i=j=0;
while(i<n)
{
next_step();
}
}
};
int main()
{
freopen("input","r",stdin);
freopen("output","w",stdout);
string pat;
cin>>pat;
string s;
cin>>s;
presuff slover;
slover.build(pat);
slover.kmp(s);
if(slover.poz.size()>1000)
{
slover.poz.resize(1000);
}
cout<<slover.poz.size()<<"\n";
for(auto &it:slover.poz)
{
cout<<it<<" ";
}
cout<<"\n";
return 0;
}