Category Archives: String Manipulation

UVA – 11512 – GATTACA – [Suffix Array]

#include <cstdio>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 100100;

struct SuffixArray {
	pair<int, int> sf[MAXN];
	int sa[MAXN], r[MAXN], height[MAXN], h[MAXN];

	struct mycmp {
		pair<int, int> * suffix;
		mycmp(pair<int, int> * suffix_) :
			suffix(suffix_) {
		}
		bool operator()(int lhs, int rhs) {
			return suffix[lhs] < suffix[rhs];
		}
	};

	void init(int n, const char a[MAXN]) {
		sa[0] = 0; // n = 1
		for (int i = 0; i < n; ++i)
			r[i] = a[i];

		for (int i, m = 1; m < n; m <<= 1) {
			for (i = 0; i < n; sa[i] = i++)
				sf[i] = make_pair(r[i], i + m < n ? r[i + m] : -1);
			sort(sa, sa + n, mycmp(sf));
			for (i = 1, r[sa[0]] = 0; i < n; ++i)
				r[sa[i]] = sf[sa[i]] != sf[sa[i - 1]] ? i : r[sa[i - 1]];
		}

		for (int i = 0; i < n; ++i) {
			if (r[i] == 0) {
				h[i] = 0;
			} else {
				int x = i, y = sa[r[i] - 1], z = max(0, h[i - 1] - 1);
				while (x + z < n && y + z < n && a[x + z] == a[y + z]) {
					++z;
				}
				h[i] = z;
			}
		}
		for (int i = 0; i < n; ++i) {
			height[i] = h[sa[i]];
		}
	}
} sa;

int main() {
	char s[1005];
	int T;
	scanf("%d", &T);
	while (T--) {
		scanf("%s", s);
		int len = strlen(s);
		sa.init(len, s);
		int maxlen = 0, maxi = 0, cnt = 0;
		for (int i = 1; i < len; i++) {
			if (sa.height[i] && sa.height[i] > maxlen) {
				maxlen = sa.height[i], maxi = i, cnt = 2;
			} else if (sa.height[i] && sa.height[i] == maxlen) {
				if (sa.height[i] == sa.height[i - 1])
					cnt++;
			}
		}
		if (cnt == 0)
			printf("%s\n", "No repetitions found!");
		else {
			for (int i = sa.sa[maxi], c = 0; c < maxlen; i++, c++)
				putchar(s[i]);
			printf(" %d\n", cnt);
		}

	}
}
</pre>
Advertisements

UVA – 10679 – I Love Strings!! – [Suffix Array nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int find(char * p) {
	int l = 0, sz = strlen(p), h = strlen(str) - 1;

	while (l <= h) {
		int mid = l + (h - l) / 2;
		char * tmp = (char*)malloc(sz+1);
		strncpy(tmp, str + pos[mid], sz);
		tmp[sz] = 0;
		int cmp = strcmp(p, tmp);
		if (cmp < 0)
			h = mid - 1;
		if (cmp > 0)
			l = mid + 1;
		if (!cmp)
			return mid;
	}
	return -1;
}

int main() {
	freopen("input.txt", "r", stdin);
	string s;
	int T, q;
	char p[2000], tmp[200];
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		scanf("%d", &q);
		gets(tmp);
		long long len = 0LL + strlen(str);
		suffixSort(len);
		while (q--) {
			gets(p);
			if (find(p) != -1)
				puts("y");
			else
				puts("n");
		}

	}
}

SPOJ – 705 – New Distinct Substrings – [Suffix Arrays nlgn]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int main() {
	string s;
	int T;
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		long long len = 0LL + strlen(str);
		long long total = len*(len+1)/2;
		suffixSort(len);
		getHeight(len);
 
		for (int i = 0; i < len; i++) 
			total -=   height[i];
		
		cout << total << endl;
	}
}

SPOJ – 649 – Distinct Substrings – [Suffix Arrays (nlgn)]

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
 
using namespace std;
 
//  O(n log n) - Manber and Myers 
 
#define N 1000005
char str[N]; //input
int rank[N], pos[N]; //output

int cnt[N], next[N]; 
bool bh[N], b2h[N];
 

bool smaller_first_char(int a, int b) {
	return str[a] < str[b];
}
 
void suffixSort(int n) {
	for (int i = 0; i < n; ++i) {
		pos[i] = i;
	}
	sort(pos, pos + n, smaller_first_char);

 
	for (int i = 0; i < n; ++i) {
		bh[i] = i == 0 || str[pos[i]] != str[pos[i - 1]];
		b2h[i] = false;
	}
 
	for (int h = 1; h < n; h <<= 1) {
		int buckets = 0;
		for (int i = 0, j; i < n; i = j) {
			j = i + 1;
			while (j < n && !bh[j])
				j++;
			next[i] = j;
			buckets++;
		}
		if (buckets == n)
			break; 

 
		for (int i = 0; i < n; i = next[i]) {
			cnt[i] = 0;
			for (int j = i; j < next[i]; ++j) {
				rank[pos[j]] = i;
			}
		}
 
		cnt[rank[n - h]]++;
		b2h[rank[n - h]] = true;
		for (int i = 0; i < n; i = next[i]) {
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0) {
					int head = rank[s];
					rank[s] = head + cnt[head]++;
					b2h[rank[s]] = true;
				}
			}
			for (int j = i; j < next[i]; ++j) {
				int s = pos[j] - h;
				if (s >= 0 && b2h[rank[s]]) {
					for (int k = rank[s] + 1; !bh[k] && b2h[k]; k++)
						b2h[k] = false;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			pos[rank[i]] = i;
			bh[i] |= b2h[i];
		}
	}
	for (int i = 0; i < n; ++i) {
		rank[pos[i]] = i;
	}
}
 
 
// O(n) - lcp - "Arrays and Its Applications" by Toru Kasai, Gunho Lee

int height[N];
// height[i] = lcp of suffix pos[i] and suffix pos[i-1]
// height[0] = 0
void getHeight(int n) {
	for (int i = 0; i < n; ++i)
		rank[pos[i]] = i;
	height[0] = 0;
	for (int i = 0, h = 0; i < n; ++i) {
		if (rank[i] > 0) {
			int j = pos[rank[i] - 1];
			while (i + h < n && j + h < n && str[i + h] == str[j + h])
				h++;
			height[rank[i]] = h;
			if (h > 0)
				h--;
		}
	}
}

 
int main() {
	string s;
	int T;
	scanf("%d", &T);
	gets(str);
	while (T--) {
		gets(str);
		long long len = 0LL + strlen(str);
		long long total = len*(len+1)/2;
		suffixSort(len);
		getHeight(len);
 
		for (int i = 0; i < len; i++) 
			total -=   height[i];
		
		cout << total << endl;
	}
}

USACO 3.2.5 – Magic Squares

#include <cstdio>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
int main() {
	freopen("msquare.in", "r", stdin), freopen("msquare.out", "w", stdout);
	string f="        ", s="12345678",seq,st,en,rev;
	char c; map<string, int> v;

	for(int i=0;i<8;i++,getchar()) f[i]= getchar();

	queue<string> q; q.push(s), q.push("");
	while(q.size()){
		s=q.front(), q.pop(), seq = q.front(), q.pop();
		if(v[s]++) continue;
		if(s==f){
			printf("%d\n%s\n", seq.size(), seq.c_str());
			return 0;
		}
		rev=string(s.rbegin(), s.rend());
		q.push(rev), q.push(seq+'A');

		st=s.substr(0,4),en=s.substr(4,4);
		rotate(st.begin(), st.begin()+3, st.end()),rotate(en.begin(),en.begin()+1,en.end());
		q.push(st+en), q.push(seq+'B');

		c =s[1],s[1]=s[6],s[6]=s[5],s[5]=s[2],s[2]=c;
		q.push(s), q.push(seq+'C');
	}
	puts("NONE");
}

USACO 3.1.5 – Contact


/*
 ID: mohmdad5
 PROG: contact
 LANG: C++
 */
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

struct Pattern { int pattern, count; };
bool operator <(const Pattern& a, const Pattern& b) {
	return a.count == b.count ? a.pattern < b.pattern : a.count > b.count;
}
void print(int num) {
	if (num <= 1) return;
	print(num / 2), putchar('0' + (num % 2));
}
int main() {
	freopen("contact.in", "r", stdin), freopen("contact.out", "w", stdout);
	char x[200001];
	int count[20000] = {0}, mask, a, b, n, A_min, B_max, L=1, i, j, top = 0, inLine = 0, N = 0;
	Pattern patterns[20001];
	cin >> a >> b >> n;
	A_min = 1 << (a), B_max = (1 << (b + 1)) - 1;
	while (cin >> x[L])
		L++;

	for (i = 0; i < L; i++)
		for (j = 1, mask = 1L; j <= b && i + j < L; j++)
			mask = (mask << 1) + (x[i + j] - '0'), count[mask] += j >= a;

	for (int i = A_min; i <= B_max; i++)
		if (count[i])
			patterns[top++] = Pattern { i, count[i] };

	sort(patterns, patterns + top);

	printf("%d\n", patterns[0].count), print(patterns[0].pattern);
	for (int i = 1; i < top; i++) {
		if (patterns[i].count != patterns[i - 1].count && !(inLine = 0) && ++N) {
			if (N >= n) break;
			printf("\n%d\n", patterns[i].count);
		} else
			putchar(inLine == 5 ? '\n' : ' '), inLine = (inLine + 1) % 6;
		print(patterns[i].pattern);
	}
	puts("");
}

USACO 1.5.3 – SuperPrime Rib


#include <iostream>
#include <cstdio>
using namespace std;

typedef long long int LL;

int isp(LL n) {
	if (n == 1) return 0;
	for (LL i = 2; i * i <= n; i++)
		if (!(n % i)) return 0;
	return 1;
}
void dfs(LL n, int d, int D){
	if(!isp(n))
		return;
	if(d==D)
		printf("%lld\n", n);
	else
		for(int i=1; i<10; i+=2)
			dfs(n*10+i, d+1, D);

}

int main() {
	int D;
	freopen("sprime.in", "r", stdin), freopen("sprime.out", "w", stdout);
	scanf("%d", &D);
	dfs(2, 1, D), dfs(3, 1, D), dfs(5, 1, D), dfs(7, 1, D);
	return 0;
}

USACO 1.5.2 – Prime Palindromes


/*
 ID: mohmdad5
 PROG: pprime
 LANG: C++
 */

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long int LL;

int isp(LL n) {
	if (n == 1) return 0;
	for (LL i = 2; i * i <= n; i++)
		if (!(n % i)) return 0;
	return 1;
}

int main() {
	int a, b;
	freopen("pprime.in", "r", stdin), freopen("pprime.out", "w", stdout);
	scanf("%d %d", &a, &b);
	for (LL n = 0; n < 10000; n++) {
		LL number = n, rem = 0, reverse = 0, pdrome, no_digits = 1;
		while (number != 0)
			reverse = reverse * 10 + number % 10, number /= 10 , no_digits *= 10;
		pdrome = n <= 9 ? n : (no_digits / 10) * n + reverse % (no_digits / 10);

		if (n == 10 && 11 >= a && 11 <= b) printf("%d\n", 11);  // 11 is the only even palindrome
		if (pdrome >= a && pdrome <= b && isp(pdrome)) printf("%lld\n", pdrome);
	}
	return 0;
}

USACO 1.3.3 – Calf Flac


int main() {
	ofstream fout("calfflac.out");
	ifstream fin("calfflac.in");
	int i, a, b, best = 0, best_a, best_b, l, b_l, a_l, spoiled;
	string s;
	char line[3000];
	while (fin.getline(line, 3000))
		s += string(line) + "\n";

	for (i = 0; i < s.size(); i++) {
		a = b = a_l = b_l = i, l = 0;
		while (a >= 0 && b < s.size()) {
			if (!isalpha(s[a]) || !isalpha(s[b])) {
				a -= !isalpha(s[a]), b += !isalpha(s[b]);
				continue;
			}
			if (tolower(s[a--]) != tolower(s[b++]))
				break;
			else
				a_l = a, b_l = b, l += 1 + (a + 1 != b - 1);
		}
		if (l > best)
			best = l, best_a = a_l, best_b = b_l;
	}

	fout << best << endl;
	if (best)
		fout << s.substr(best_a + 1, best_b - best_a - 1) << endl;
	return 0;
}

UVA – 594 – One Little, Two Little, Three Little Endians

  • Problem Statement : http://uva.onlinejudge.org/external/5/594.html
  • Type : bitwise
  • Hint : instead of traversing through bits and handling the reverse process, you can just convert the pointer to a char * and swap the 1st and the 4th and the 2nd with the 3rd. 🙂
<pre>#include<stdio.h>
using namespace std;
#define SWAP(a,b) a= a^b, b=a^b, a=a^b
int main() {
	int o, reverse;
	while (scanf("%d", &o) == 1) {
		reverse = o;
		char * bits = (char*) &reverse;
		SWAP(bits[0], bits[3]), SWAP(bits[1], bits[2]);
		printf("%d converts to %d\n", o, reverse);
	}
	return 0;
}