Hashing

 Resources:

Threads @ IIIT Hyderabad

Palindrome Substring Queries

Palindrome Substring Queries Implementation

CF blog

CF blog

E-maxx

uniqeSubstring Implementation 

group identical implementation 

Problems:

Substring Search 

1517. Freedom of Choice

ADAPHOTO - Ada and Terramorphing 

Minimal Shift 

Cyclic Shifts 

Sub-palindromes

Manacher's Algorithm 

Strings - 3 

Suffixes 

Jitu and Strings   

A2 online 

H. Queries for Number of Palindromes

Implementation:

	///https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=42&id_problem=262&locale=en
	/// Topic: hashing
	/// O(n+m)
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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++) {
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	scanf("%s", ch);
	string b(ch);
	const int mxpow = max(a.size(), b.size());
	Hash::base = gen_base(256, Hash::mod);
	Hash hash_a(a), hash_b(b);
	//Copy needed hash from all string b:
	const auto need = hash_b(0, (int)b.size(), mxpow);
	//dbg(need);
	for (int i = 0; i + (int)b.size() <= (int)a.size(); i++) {
	if (hash_a(i, b.size(), mxpow) == need) {
	printf("%d ", i);
	}
	}
	}
	return 0;
	}

view raw 1.Substring Search.cpp hosted with ❤ by GitHub

	///http://acm.timus.ru/problem.aspx?space=1&num=1517
	// O(n log(n)^2)
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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;
	scanf("%d", &n);
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	scanf("%s", ch);
	string b(ch);
	const int mxpow = max(a.size(), b.size());
	Hash::base = gen_base(256, Hash::mod);
	Hash hash_a(a), hash_b(b);
	int pos = -1, lw = 0, hi = min(a.size(), b.size()) + 1;
	while (hi - lw > 1) {
	int mid = (lw + hi) / 2;
	vector<pair<int, ull>> hashes;
	for (int i = 0; i + mid <= n; i++) {
	hashes.push_back(hash_a(i, mid, mxpow));
	}
	sort(hashes.begin(), hashes.end());
	int p = -1;
	for (int i = 0; i + mid <= n; i++) {
	if (binary_search(hashes.begin(), hashes.end(), hash_b(i, mid, mxpow))) {
	p = i;
	break;
	}
	}
	if (p >= 0) {
	lw = mid;
	pos = p;
	}
	else {
	hi = mid;
	}
	}
	assert(pos >= 0);
	printf("%s\n", b.substr(pos, lw).c_str());
	}
	return 0;
	}

view raw 2.Freedom of Choice.cpp hosted with ❤ by GitHub

	///https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=43&id_problem=284&locale=en
	///nlog(n)
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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++) {
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	int n = a.size();
	a += a;
	const int mxpow = 2 * n;
	Hash::base = gen_base(256, Hash::mod);
	Hash hash(a);
	vector<int> pos;
	for (int i = 0; i < n; i++) {
	pos.push_back(i);
	}
	auto p = *min_element(pos.begin(), pos.end(), [&](const int p1, const int p2) {
	int lw = 0, hi = n + 1;
	while (hi - lw > 1) {
	int mid = (lw + hi) / 2;
	if (hash(p1, mid, mxpow) == hash(p2, mid, mxpow))
	lw = mid;
	else hi = mid;
	}
	return lw < n && a[p1 + lw] < a[p2 + lw];
	});
	printf("%s\n", a.substr(p, n).c_str());
	}
	return 0;
	}

view raw 3.Minimal Shift.cpp hosted with ❤ by GitHub

	///https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=43&id_problem=286&locale=en
	/// O(n log(n)^2)
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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++) {
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	int n = a.size();
	a += a;
	const int mxpow = 2 * n;
	Hash::base = gen_base(256, Hash::mod);
	Hash hash(a);
	vector<int> pos;
	for (int i = 0; i < n; i++) {
	pos.push_back(i);
	}
	stable_sort(pos.begin(), pos.end(), [&](const int p1, const int p2) {
	int lw = 0, hi = n + 1;
	while (hi - lw > 1) {
	int mid = (lw + hi) / 2;
	if (hash(p1, mid, mxpow) == hash(p2, mid, mxpow))
	lw = mid;
	else hi = mid;
	}
	return lw < n && a[p1 + lw] < a[p2 + lw];
	});
	printf("%d\n", (int)(find(pos.begin(), pos.end(), 0) - pos.begin() ) + 1);
	string ans;
	for (auto x : pos)
	{
	ans.push_back(a[x + n - 1]);
	}
	printf("%s\n", ans.c_str());
	}
	return 0;
	}

view raw 4.Cyclic Shifts.cpp hosted with ❤ by GitHub

	///https://acmp.ru/asp/do/index.asp?main=task&id_course=2&id_section=18&id_topic=43&id_problem=285&locale=en
	///nlog(n)
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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++) {
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	int n = a.size();
	string b(a);
	reverse(b.begin(), b.end());
	// const int mxpow = 2 * n;
	Hash::base = gen_base(256, Hash::mod);
	Hash hash_a(a) , hash_b(b);
	vector<int> pos;
	for (int i = 0; i < n; i++) {
	pos.push_back(i);
	}
	ull ans = 0;
	for (int i = 0, j = n - 1; i < n; ++i, --j) {
	// odd length
	int lw = 0, hi = min(n - i, n - j) + 1;
	while (hi - lw > 1) {
	int mid = (lw + hi) / 2;
	if (hash_a(i, mid, n) == hash_b(j, mid, n))
	lw = mid;
	else hi = mid;
	}
	ans += lw;
	/// even length
	lw = 0, hi = min(n - i - 1, n - j) + 1;
	while (hi - lw > 1) {
	int mid = (lw + hi) / 2;
	if (hash_a(i + 1, mid, n) == hash_b(j, mid, n))
	lw = mid;
	else hi = mid;
	}
	ans += lw;
	}
	cout << ans << endl;
	}
	return 0;
	}

view raw 5.Sub-palindromes.cpp hosted with ❤ by GitHub

	///https://acmp.ru/index.asp?main=task&id_task=829
	///Solution: polynomial hashes, sort, binary search, O(n log(n))
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = (int) 1e9 + 123;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(1LL * pw1.back() * base % mod);
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = (pref1[i] + 1LL * s[i] * pw1[i]) % mod;
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = pref1[pos + len] - pref1[pos];
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (hash1 < 0) hash1 += mod;
	if (mxpow != 0) {
	hash1 = 1LL * hash1 * pw1[mxpow - (pos + len - 1)] % mod;
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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++) {
	char ch[100005];
	scanf("%s", ch);
	string a(ch);
	scanf("%s", ch);
	string b(ch);
	const int mxpow = max(a.size(), b.size() * 2);
	Hash::base = gen_base(256, Hash::mod);
	Hash hash_a(a) , hash_b(b+b);
	vector<pair<int, ull>> hashes;
	for (int i = 0; i < (int)b.size(); i++) {
	hashes.push_back(hash_b(i, b.size(), mxpow));
	}
	sort(hashes.begin(), hashes.end());
	int ans = 0;
	for (int i = 0; i + (int)b.size() <= (int)a.size(); i++) {
	ans += binary_search(hashes.begin(), hashes.end(), hash_a(i, b.size(), mxpow));
	}
	cout << ans << endl;
	}
	return 0;
	}

view raw 6.Strings - 3.cpp hosted with ❤ by GitHub

	///https://www.hackerrank.com/contests/ab-yeh-kar-ke-dikhao/challenges/jitu-and-strings/problem
	///Solution: polynomial hashes,binary search, O(n log(n))
	#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;
	/**___________________________________________________**/
	typedef unsigned long long ull;
	// Generate random base in (before, after) open interval:
	int gen_base(const int before, const int after) {
	auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
	std::mt19937 mt_rand(seed);
	int base = std::uniform_int_distribution<int>(before + 1, after)(mt_rand);
	return base % 2 == 0 ? base - 1 : base;
	}
	struct Hash
	{
	static const int mod = 2147483647;
	static vector<int> pw1; // powers of base modulo mod
	static vector<ull> pw2; // powers of base modulo 2^64
	static int base;
	static inline int diff(int a, int b)
	{
	return (a -= b) < 0 ? a + mod : a;
	}
	static inline int MOD(ull x)
	{
	x += mod;
	x = (x >> 31) + (x & mod);
	return int((x >> 31) + (x & mod));
	}
	vector<int> pref1; // powers of base modulo mod
	vector<ull> pref2; // powers of base modulo 2^64
	Hash(const string& s)
	: pref1(s.size() + 1u, 0)
	, pref2(s.size() + 1u, 0)
	{
	assert(base < mod);
	const int n = s.size(); // firstly calculated needed power of base
	while ((int)pw1.size() <= n) {
	pw1.push_back(MOD((ull)pw1.back()*base));
	pw2.push_back(pw2.back() * base);
	}
	for (int i = 0; i < n; i++) {
	assert(base > s[i]);
	pref1[i + 1] = MOD(pref1[i] + (ull)s[i] * pw1[i]);
	pref2[i + 1] = pref2[i] + s[i] * pw2[i];
	}
	}
	// Polynomial hash of subsequence [pos, pos+len)
	// If mxPow != 0, value automatically multiply on base in needed power. Finally base ^ mxPow
	inline pair<int, ull> operator()(const int pos, const int len, const int mxpow = 0)const {
	int hash1 = diff(pref1[pos + len] , pref1[pos]);
	ull hash2 = pref2[pos + len] - pref2[pos];
	if (mxpow != 0) {
	hash1 = MOD((ull) hash1 * pw1[mxpow - (pos + len - 1)]);
	hash2 *= pw2[mxpow - (pos + len - 1)];
	}
	return {hash1, hash2};
	}
	inline pair<int, ull> prefix_after_swap(const int len, const int i, const int j, const char ci, const char cj) const {
	// prefix before i:
	int hash1 = pref1[min(len, i)];
	ull hash2 = pref2[min(len, i)];
	if (len <= i) return {hash1, hash2};
	// add symbol on position i after swap
	hash1 = MOD(hash1 + (ull)cj * pw1[i]);
	hash2 += cj * pw2[i];
	// Prefix prefore j:
	hash1 = MOD(hash1 + (ull)diff(pref1[min(len, j)], pref1[i + 1]));
	hash2 += pref2[min(len, j)] - pref2[i + 1];
	if (len <= j) return {hash1, hash2};
	// Add symbol on position j after swap:
	hash1 = MOD(hash1 + (ull)ci * pw1[j]);
	hash2 += ci * pw2[j];
	// Prefix before len:
	hash1 = MOD(hash1 + (ull)diff(pref1[len], pref1[j + 1]));
	hash2 += pref2[len] - pref2[j + 1];
	return {hash1, hash2};
	}
	};
	int Hash::base(1e9 + 7);
	vector<int> Hash::pw1{1};
	vector<ull> Hash:: pw2{1};
	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;
	scanf("%d", &n);
	char ch[200005];
	scanf("%s", ch);
	string a(ch);
	scanf("%s", ch);
	string b(ch);
	//const int mxpow = max(a.size(), b.size() * 2);
	Hash::base = gen_base(256, Hash::mod);
	Hash hash_a(a) , hash_b(b);
	int pos1 = 0;
	while (pos1 < n && a[pos1] == b[pos1]) ++pos1;
	int ans = pos1;
	for (int pos2 = pos1 + 1; pos2 < n; pos2++) {
	int lw = 0, hi = n + 1;
	while (hi - lw > 1) {
	const int mid = (lw + hi) / 2;
	const auto hs = hash_a.prefix_after_swap(mid, pos1, pos2, a[pos1], a[pos2]);
	if (hs == hash_b(0, mid))
	lw = mid;
	else hi = mid;
	}
	ans = max(ans, lw);
	}
	cout << ans << endl;
	}
	return 0;
	}

view raw Jitu and Strings.cpp hosted with ❤ by GitHub

 

Share: