Scribd
Upload
27 views3 pages

Code

The document contains C++ code implementing the Knuth-Morris-Pratt (KMP) algorithm for substring search. It reads two integers, constructs strings from the range between them, and uses KMP to find the occurrences of a concatenated string. The result is printed as the number of occurrences divided by the length of the generated strings plus one.

Uploaded by

duyanh25012010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
27 views3 pages

Code

The document contains C++ code implementing the Knuth-Morris-Pratt (KMP) algorithm for substring search. It reads two integers, constructs strings from the range between them, and uses KMP to find the occurrences of a concatenated string. The result is printed as the number of occurrences divided by the length of the generated strings plus one.

Uploaded by

duyanh25012010
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

#pragma GCC optimize("Ofast")

#pragma GCC optimize("O2")


#include<bits/stdc++.h>
#include<ios>
#include<iostream>
#include<iosfwd>
#include<iomanip>
#include<istream>
#include<ostream>
#include<sstream>
#include<streambuf>
#include<complex>
#include<numeric>
#include<valarray>
#include<string>
#include<bitset>
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<iterator>
#include<locale>
#include<memory>
#include<stdexcept>
#include<utility>
#include<exception>
#include<limits>
#include<new>
#include<typeinfo>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<climits>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdlib>
#include<cstddef>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cwchar>
#include<cwctype>
#define faster ios_base::sync_with_stdio(0);[Link](0);[Link](0);
#define db double
#define ldb long double
#define bo bool
#define vo void
#define ch char
#define uc unsigned char
#define sc signed char
#define fl float
#define ui unsigned int
#define si signed int
#define shi short int
#define ushi unsigned short int
#define sshi sign short int
#define li long int
#define sli signed long int
#define ll long long
#define str string
#define re return
using namespace std;
vector<ll> LPS(const str &a)
{
ll m=[Link](),d=0,i=1;
vector<ll> b(m,0);
while(i<m)
{
if(a[i]==a[d])
{
d++;
b[i]=d;
i++;
}
else
{
if(d!=0) d=b[d-1];
else
{
b[i]=0;
i++;
}
}
}
re b;
}
ll KMP(const str &s, const string &a)
{
ll n=[Link](),m=[Link](),i=0,j=0;
vector<ll> b=LPS(a);
while(i<n)
{
if(s[i]==a[j])
{
i++;
j++;
}
if(j==m) re i-j;
else if(i<n&&s[i]!=a[j])
{
if (j!=0) j=b[j-1];
else i++;
}
}
re -1;
}
int main()
{
ll a,b,i,r;
cin>>a>>b;
str s1="",s2="",ex;
vector<str> n;
for(i=a;i<=b;i++) n.push_back(to_string(i));
vector<str> s=n;
sort([Link](),[Link]());
for(const str &i:n) s1+=i+"#";
for(const str &i:s) s2+=i+"#";
ex=s2+s2;
r=KMP(ex,s1);
cout<<r/(n[0].size()+1);
}

You might also like