Mai intai trebuie sa te autentifici.
Cod sursa(job #3292231)
Utilizator | Data | 7 aprilie 2025 17:27:27 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.27 kb |
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fcin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
inline vector <int> precalc(const string &s)
{
vector <int> rez(s.size());
int i=1, j=0; rez[0]=0;
while(i<s.size())
{
if(s[i]==s[j])
{
j++;
rez[i]=j;
i++;
}
else
{
if(j!=0)
{
j=rez[j-1];
}
else
{
rez[i]=0;
i++;
}
}
}
return rez;
}
inline void kmp(const string &a, const string &b)
{
vector <int> lps, rez;
lps=precalc(a);
int i=0, j=0;
while(i<b.size())
{
if(b[i]==a[j])
{
i++;
j++;
}
else
{
if(j!=0)
{
j=lps[j-1];
}
else
{
i++;
}
}
if(j==a.size())
{
rez.push_back(i-a.size());
}
}
fout<<rez.size()<<'\n';
for(auto i : rez)
fout<<i<<" ";
}
int main()
{
fcin>>a>>b;
kmp(a,b);
return 0;
}