Resources:
স্ট্রিং ম্যাচিং: নুথ-মরিসন-প্র্যাট (কেএমপি) অ্যালগরিদম
LoveExtendsCode
Tanvir blog
KMP অ্যালগোরিদম
Tushar Roy
KMP (E-maxx)
Knuth-Morris-Pratt algorithm
TopCoder blog
medium blog
BTech blog
Implementation:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Not Tested
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg1(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
os << "{";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin() ) os << ", ";
os << *it;
}
return os << "}";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin()) os << ", ";
os << *it;
}
return os << "]";
}
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin() ) os << ", ";
os << it -> first << " = " << it -> second ;
}
return os << "]";
}
#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
void faltu () { cerr << endl; }
template <typename T>
void faltu( T a[], int n ) {
for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
cerr << endl;
}
template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
// Program showing a policy-based data structure.
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
// GNU link : https://goo.gl/WVDL6g
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>
new_data_set;
/**___________________________________________________**/
const int N = 2e5 + 5;
string s;
int pf[N];
const int Mod = 10007;
void lps()
{
pf[0] = 0;
for (int i = 1; i < (int)s.length(); i++) {
int j = pf[i - 1];
while (j > 0 && s[i] != s[j]) j = pf[j - 1];
if (s[i] == s[j]) ++j;
pf[i] = j;
}
}
int main()
{
//FASTIO
///*
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
//*/
int T;
scanf("%d", &T);
//T = 1;
for (int cs = 1; cs <= T; cs++) {
int n;
cin >> n >> s;
lps();
int ans = n;
for (int i = 1; i < n; i++) {
int j = pf[i];
while (j > 0) {
ans ++;
j = pf[j - 1];
ans %= Mod;
}
}
cout << (ans % Mod) << endl;
}
return 0;
}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 1000005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
// #define dbg1(x) cerr << #x << " = " << x << endl;
// #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
// #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
// #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
// template < typename F, typename S >
// ostream& operator << ( ostream& os, const pair< F, S > & p ) {
// return os << "(" << p.first << ", " << p.second << ")";
// }
// template < typename T >
// ostream &operator << ( ostream & os, const vector< T > &v ) {
// os << "{";
// for (auto it = v.begin(); it != v.end(); ++it) {
// if ( it != v.begin() ) os << ", ";
// os << *it;
// }
// return os << "}";
// }
// template < typename T >
// ostream &operator << ( ostream & os, const set< T > &v ) {
// os << "[";
// for (auto it = v.begin(); it != v.end(); ++it) {
// if ( it != v.begin()) os << ", ";
// os << *it;
// }
// return os << "]";
// }
// template < typename F, typename S >
// ostream &operator << ( ostream & os, const map< F, S > &v ) {
// os << "[";
// for (auto it = v.begin(); it != v.end(); ++it) {
// if ( it != v.begin() ) os << ", ";
// os << it -> first << " = " << it -> second ;
// }
// return os << "]";
// }
// #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
// clock_t tStart = clock();
// #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
// void faltu () { cerr << endl; }
// template <typename T>
// void faltu( T a[], int n ) {
// for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
// cerr << endl;
// }
// template <typename T, typename ... hello>
// void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
// // Program showing a policy-based data structure.
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp>
// #include <functional> // for less
// #include <iostream>
// using namespace __gnu_pbds;
// using namespace std;
// // GNU link : https://goo.gl/WVDL6g
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
// tree_order_statistics_node_update>
// new_data_set;
// /**___________________________________________________**/
int n, m;
char p[maxn];
char q[maxn];
int a[maxn];
void preprocess(char *str)
{
int i = 0, j = -1;
a[i] = j;
while (i < m) {
while (j >= 0 && str[i] != str[j])
j = a[j];
i++;
j++;
a[i] = j;
}
}
int kmp(char *str, char *s, int *a)
{
int i = 0, j = 0;
while (i < n) {
while (j >= 0 && str[i] != s[j])
j = a[j];
i++;
j++;
}
return j;
}
int main()
{
//FASTIO
///*
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
//*/
int T;
scanf("%d", &T);
getchar();
//T = 1;
for (int cs = 1; cs <= T; cs++) {
scanf("%s", p);
n = m = strlen(p);
reverse_copy(p, p + n, q);
preprocess(q);
int x = kmp(p, q, a);
printf("Case %d: %d\n", cs, 2 * n - x);
}
return 0;
}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 1000006
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg1(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
/*
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
os << "{";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin() ) os << ", ";
os << *it;
}
return os << "}";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin()) os << ", ";
os << *it;
}
return os << "]";
}
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
os << "[";
for (auto it = v.begin(); it != v.end(); ++it) {
if ( it != v.begin() ) os << ", ";
os << it -> first << " = " << it -> second ;
}
return os << "]";
}
#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
clock_t tStart = clock();
#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
void faltu () { cerr << endl; }
template <typename T>
void faltu( T a[], int n ) {
for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
cerr << endl;
}
template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
// Program showing a policy-based data structure.
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
#include <iostream>
using namespace __gnu_pbds;
using namespace std;
// GNU link : https://goo.gl/WVDL6g
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
tree_order_statistics_node_update>
new_data_set;
*/
/**___________________________________________________**/
vector<int> LPS(string pattern)
{
vector<int> lps(pattern.length());
int idx = 0;
for (int i = 1; i < (int)pattern.length();) {
if (pattern[i] == pattern[idx]) {
lps[i] = ++idx;
i++;
}
else {
if (idx != 0) idx = lps[idx - 1];
else lps[i] = idx, ++i;
}
}
return lps;
}
void KMP(string text, string pattern)
{
//bool found = false;
vector<int> lps = LPS(pattern);
int j = 0; // pattern
int i = 0; // text
int ans = 0;
while (i < (int)text.length())
{
if (text[i] == pattern[j]) {
i++;
j++;
}
else {
if (j != 0) j = lps[j - 1];
else ++i;
}
if (j == (int)pattern.length()) {
ans++;
//cout << "found match at : " << (i - pattern.length()) << endl;
j = lps[j - 1];
//found = true;
}
}
//if (!found) cout << "Not found\n";
printf("%d\n", ans);
}
char text[maxn], pattern[maxn];
int main()
{
FASTIO
///*
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
//*/
int T;
scanf("%d", &T);
//T = 1;
for (int cs = 1; cs <= T; cs++) {
scanf("%s %s", text, pattern);
printf("Case %d: ", cs);
KMP(text, pattern);
}
return 0;
}
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Not Tested | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 100005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| template < typename F, typename S > | |
| ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| return os << "(" << p.first << ", " << p.second << ")"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| os << "{"; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << *it; | |
| } | |
| return os << "}"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const set< T > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin()) os << ", "; | |
| os << *it; | |
| } | |
| return os << "]"; | |
| } | |
| template < typename F, typename S > | |
| ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << it -> first << " = " << it -> second ; | |
| } | |
| return os << "]"; | |
| } | |
| #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| clock_t tStart = clock(); | |
| #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| void faltu () { cerr << endl; } | |
| template <typename T> | |
| void faltu( T a[], int n ) { | |
| for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| cerr << endl; | |
| } | |
| template <typename T, typename ... hello> | |
| void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // Program showing a policy-based data structure. | |
| #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| #include <ext/pb_ds/tree_policy.hpp> | |
| #include <functional> // for less | |
| #include <iostream> | |
| using namespace __gnu_pbds; | |
| using namespace std; | |
| // GNU link : https://goo.gl/WVDL6g | |
| typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| tree_order_statistics_node_update> | |
| new_data_set; | |
| /**___________________________________________________**/ | |
| const int N = 2e5 + 5; | |
| string s; | |
| int pf[N]; | |
| const int Mod = 10007; | |
| void lps() | |
| { | |
| pf[0] = 0; | |
| for (int i = 1; i < (int)s.length(); i++) { | |
| int j = pf[i - 1]; | |
| while (j > 0 && s[i] != s[j]) j = pf[j - 1]; | |
| if (s[i] == s[j]) ++j; | |
| pf[i] = j; | |
| } | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| //T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| int n; | |
| cin >> n >> s; | |
| lps(); | |
| int ans = n; | |
| for (int i = 1; i < n; i++) { | |
| int j = pf[i]; | |
| while (j > 0) { | |
| ans ++; | |
| j = pf[j - 1]; | |
| ans %= Mod; | |
| } | |
| } | |
| cout << (ans % Mod) << endl; | |
| } | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 1000005 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| // #define dbg1(x) cerr << #x << " = " << x << endl; | |
| // #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| // #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| // #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| // template < typename F, typename S > | |
| // ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| // return os << "(" << p.first << ", " << p.second << ")"; | |
| // } | |
| // template < typename T > | |
| // ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| // os << "{"; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin() ) os << ", "; | |
| // os << *it; | |
| // } | |
| // return os << "}"; | |
| // } | |
| // template < typename T > | |
| // ostream &operator << ( ostream & os, const set< T > &v ) { | |
| // os << "["; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin()) os << ", "; | |
| // os << *it; | |
| // } | |
| // return os << "]"; | |
| // } | |
| // template < typename F, typename S > | |
| // ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| // os << "["; | |
| // for (auto it = v.begin(); it != v.end(); ++it) { | |
| // if ( it != v.begin() ) os << ", "; | |
| // os << it -> first << " = " << it -> second ; | |
| // } | |
| // return os << "]"; | |
| // } | |
| // #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| // clock_t tStart = clock(); | |
| // #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| // void faltu () { cerr << endl; } | |
| // template <typename T> | |
| // void faltu( T a[], int n ) { | |
| // for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| // cerr << endl; | |
| // } | |
| // template <typename T, typename ... hello> | |
| // void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // // Program showing a policy-based data structure. | |
| // #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| // #include <ext/pb_ds/tree_policy.hpp> | |
| // #include <functional> // for less | |
| // #include <iostream> | |
| // using namespace __gnu_pbds; | |
| // using namespace std; | |
| // // GNU link : https://goo.gl/WVDL6g | |
| // typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| // tree_order_statistics_node_update> | |
| // new_data_set; | |
| // /**___________________________________________________**/ | |
| int n, m; | |
| char p[maxn]; | |
| char q[maxn]; | |
| int a[maxn]; | |
| void preprocess(char *str) | |
| { | |
| int i = 0, j = -1; | |
| a[i] = j; | |
| while (i < m) { | |
| while (j >= 0 && str[i] != str[j]) | |
| j = a[j]; | |
| i++; | |
| j++; | |
| a[i] = j; | |
| } | |
| } | |
| int kmp(char *str, char *s, int *a) | |
| { | |
| int i = 0, j = 0; | |
| while (i < n) { | |
| while (j >= 0 && str[i] != s[j]) | |
| j = a[j]; | |
| i++; | |
| j++; | |
| } | |
| return j; | |
| } | |
| int main() | |
| { | |
| //FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| getchar(); | |
| //T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| scanf("%s", p); | |
| n = m = strlen(p); | |
| reverse_copy(p, p + n, q); | |
| preprocess(q); | |
| int x = kmp(p, q, a); | |
| printf("Case %d: %d\n", cs, 2 * n - x); | |
| } | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define INF 1<<30 | |
| #define endl '\n' | |
| #define maxn 1000006 | |
| #define tc printf("Case %d: ", cs) | |
| #define tcn printf("Case %d:\n", cs); | |
| #define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); | |
| typedef long long ll; | |
| const double PI = acos(-1.0); | |
| #define dbg1(x) cerr << #x << " = " << x << endl; | |
| #define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl; | |
| #define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| #define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl; | |
| /* | |
| template < typename F, typename S > | |
| ostream& operator << ( ostream& os, const pair< F, S > & p ) { | |
| return os << "(" << p.first << ", " << p.second << ")"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const vector< T > &v ) { | |
| os << "{"; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << *it; | |
| } | |
| return os << "}"; | |
| } | |
| template < typename T > | |
| ostream &operator << ( ostream & os, const set< T > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin()) os << ", "; | |
| os << *it; | |
| } | |
| return os << "]"; | |
| } | |
| template < typename F, typename S > | |
| ostream &operator << ( ostream & os, const map< F, S > &v ) { | |
| os << "["; | |
| for (auto it = v.begin(); it != v.end(); ++it) { | |
| if ( it != v.begin() ) os << ", "; | |
| os << it -> first << " = " << it -> second ; | |
| } | |
| return os << "]"; | |
| } | |
| #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0) | |
| clock_t tStart = clock(); | |
| #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC) | |
| void faltu () { cerr << endl; } | |
| template <typename T> | |
| void faltu( T a[], int n ) { | |
| for (int i = 0; i < n; ++i) cerr << a[i] << ' '; | |
| cerr << endl; | |
| } | |
| template <typename T, typename ... hello> | |
| void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); } | |
| // Program showing a policy-based data structure. | |
| #include <ext/pb_ds/assoc_container.hpp> // Common file | |
| #include <ext/pb_ds/tree_policy.hpp> | |
| #include <functional> // for less | |
| #include <iostream> | |
| using namespace __gnu_pbds; | |
| using namespace std; | |
| // GNU link : https://goo.gl/WVDL6g | |
| typedef tree<int, null_type, less_equal<int>, rb_tree_tag, | |
| tree_order_statistics_node_update> | |
| new_data_set; | |
| */ | |
| /**___________________________________________________**/ | |
| vector<int> LPS(string pattern) | |
| { | |
| vector<int> lps(pattern.length()); | |
| int idx = 0; | |
| for (int i = 1; i < (int)pattern.length();) { | |
| if (pattern[i] == pattern[idx]) { | |
| lps[i] = ++idx; | |
| i++; | |
| } | |
| else { | |
| if (idx != 0) idx = lps[idx - 1]; | |
| else lps[i] = idx, ++i; | |
| } | |
| } | |
| return lps; | |
| } | |
| void KMP(string text, string pattern) | |
| { | |
| //bool found = false; | |
| vector<int> lps = LPS(pattern); | |
| int j = 0; // pattern | |
| int i = 0; // text | |
| int ans = 0; | |
| while (i < (int)text.length()) | |
| { | |
| if (text[i] == pattern[j]) { | |
| i++; | |
| j++; | |
| } | |
| else { | |
| if (j != 0) j = lps[j - 1]; | |
| else ++i; | |
| } | |
| if (j == (int)pattern.length()) { | |
| ans++; | |
| //cout << "found match at : " << (i - pattern.length()) << endl; | |
| j = lps[j - 1]; | |
| //found = true; | |
| } | |
| } | |
| //if (!found) cout << "Not found\n"; | |
| printf("%d\n", ans); | |
| } | |
| char text[maxn], pattern[maxn]; | |
| int main() | |
| { | |
| FASTIO | |
| ///* | |
| #ifndef ONLINE_JUDGE | |
| freopen("in.txt", "r", stdin); | |
| freopen("out.txt", "w", stdout); | |
| freopen("error.txt", "w", stderr); | |
| #endif | |
| //*/ | |
| int T; | |
| scanf("%d", &T); | |
| //T = 1; | |
| for (int cs = 1; cs <= T; cs++) { | |
| scanf("%s %s", text, pattern); | |
| printf("Case %d: ", cs); | |
| KMP(text, pattern); | |
| } | |
| return 0; | |
| } | |
No comments:
Post a Comment