hackerrank 24 link
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
char input[3000], output[3000];
int queries[600];
int malloc_cnt = 0;
//HASH table for ints implementation
typedef struct bucket_item{
int key;
char *val;
struct bucket_item *next;
} HASH_NODE;
#define HASH_MODULUS 997
HASH_NODE* hash_arr[HASH_MODULUS];
int calc_hash(int i) {
return (i % HASH_MODULUS);
}
HASH_NODE *get_hash_table_entry(int i) {
int hash = calc_hash(i);
HASH_NODE *item = hash_arr[hash];
if(item == NULL) { return NULL; }
while(item) {
if(item->key == i) { return item; }
item = item->next;
}
return NULL;
}
void insert_into_hash_table(int i) {
if(get_hash_table_entry(i) != NULL) { return; }
int hash = calc_hash(i);
HASH_NODE *new_node = malloc(sizeof(HASH_NODE));
new_node->key = i;
new_node->val = malloc(sizeof(char) * 2200);
new_node->next = NULL;
strcpy(new_node->val, "INVALID");
if(hash_arr[hash] == NULL) {
hash_arr[hash] = new_node;
} else {
new_node->next = hash_arr[hash];
hash_arr[hash] = new_node;
}
}
void print_keys_in_hash_table() {
int i;
HASH_NODE *tmp;
printf("HASH TABLE ENTRIES\n");
for(i = 0; i < HASH_MODULUS; i++) {
tmp = hash_arr[i];
while(tmp) {
printf("%d\n", tmp->key);
tmp = tmp->next;
}
}
printf("HASH TABLE ENTRIES OVER\n");
}
//
typedef struct node{
char *word;
int len;
struct node *children[26];
}NODE;
typedef void (*TRAVERSE_FUNC) (char *, int);
NODE* tree_root;
//return the length of the largest common prefix of str1, str2
int prefix_match_cnt(char * str1, char *str2, int len1, int len2) {
int i = 0;
while((i < len1) && (i < len2) && (*str1++ == *str2++)) {
i++;
}
return i;
}
NODE* create_node(char *str, int len) {
int i;
NODE *tmp = malloc(sizeof(NODE));
tmp->word = str;
tmp->len = len;
for(i = 0; i < 26; i++) {
tmp->children[i] = NULL;
}
malloc_cnt++;
return tmp;
}
void add_suffix_string_to_tree(NODE *node, NODE *par_node, char *str, int len) {
int i, match_cnt;
NODE* new_node;
if(len == 0) { return; }
if(node->len != -1) { //node->len = -1 ==> root
match_cnt = prefix_match_cnt(str, node->word, len, node->len);
if(match_cnt == len) { return; } //The string is already present in the tree. return
//we are here ==> (match_cnt < len), (match_cnt <= node->len).
str = &str[match_cnt];
len -= match_cnt;
if(match_cnt < node->len) {
//split the current node with match_cnt length
new_node = create_node(node->word, match_cnt);
par_node->children[node->word[0] - 'a'] = new_node;
node->word += match_cnt;
node->len -= match_cnt;
new_node->children[node->word[0] - 'a'] = node;
node = new_node;
}
}
i = (str[0] - 'a');
if(node->children[i] == NULL) {
node->children[i] = create_node(str, len);
} else {
add_suffix_string_to_tree(node->children[i], node, str, len);
}
}
void add_all_suffixes_to_tree(NODE *root, char *str) {
int i, len = strlen(str);
for(i = 0; i < len; i++) {
add_suffix_string_to_tree(root, NULL, &str[i], (len - i));
}
}
void traverse_all_substrings(NODE *node, char *out, int len, TRAVERSE_FUNC func) {
int i;
if(node == NULL) { return; }
if(node->len == -1) {
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len, func);
}
} else {
strncpy(&out[len], node->word, node->len);
for(i = 0; i < node->len; i++) {
func(out, len + (i + 1));
}
for(i = 0; i < 26; i++) {
traverse_all_substrings(node->children[i], out, len + (node->len), func);
}
}
}
void print_substring(char *str, int len) {
char c = str[len];
str[len] = '\0';
printf("%s\n", str);
str[len] = c;
}
int total_substr_cnt = 0;
void cnt_substrings(char *str, int len) {
total_substr_cnt++;
}
int substr_cnt = 0;
void handle_substring(char *str, int len) {
char c = str[len];
HASH_NODE *item;
substr_cnt++;
item = get_hash_table_entry(substr_cnt);
if(item) {
str[len] = '\0';
strcpy(item->val, str);
str[len] = c;
return;
}
}
char* chomp(char * str) {
int len = strlen(str);
if((len > 0) && (str[len - 1] == '\n')) { str[len - 1] = '\0'; }
if((len > 1) && (str[len - 2] == '\r')) { str[len - 2] = '\0'; }
return str;
}
char* convert_to_lower(char* str) {
int len = strlen(str), i;
for(i = 0; i < len; i++) {
str[i] = tolower(str[i]);
}
return str;
}
FILE *file_open(char *filename, char *mode) {
FILE *fp = fopen(filename, mode);
if(fp == NULL) {
perror("file_open");
exit(0);
}
return fp;
}
int main(int argc, char **argv) {
int num_words, num_queries, tmp;
char *str;
int query_idx = 0, idx;
HASH_NODE *item;
FILE *fp = stdin;
if(argc > 1) {
fp = file_open(argv[1], "r");
}
fgets(input, 3000, fp);
num_words = tmp = atoi(input);
// printf(":%d:\n", num_words);
tree_root = create_node(NULL, -1); //Root marker
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
convert_to_lower(input);
//printf("Adding \"%s\" ....", input);
str = malloc(sizeof(char) * 3000);
strcpy(str, input);
add_all_suffixes_to_tree(tree_root, str);
//printf("Done\n");
}
total_substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, cnt_substrings);
/* printf("OUTPUT:\n____________________\n");
traverse_all_substrings(tree_root, output, 0, print_substring);
printf("\n____________________\n");*/
fgets(input, 3000, fp);
num_queries = tmp = atoi(input);
// printf(":%d:\n", num_queries);
while(tmp > 0) {
tmp--;
fgets(input, 3000, fp);
chomp(input);
// printf("%s: ", input);
queries[query_idx] = atoi(input);
insert_into_hash_table(queries[query_idx]);
query_idx++;
}
// print_keys_in_hash_table();
// printf("total_substr_cnt: %d\n", total_substr_cnt);
substr_cnt = 0;
traverse_all_substrings(tree_root, output, 0, handle_substring);
for(idx = 0; idx < query_idx; idx++) {
item = get_hash_table_entry(queries[idx]);
printf("%s\n", item->val);
}
//Free all the memory if you have free time ;)
// printf("Malloc Count: %d \n", malloc_cnt);
// getchar();
return 0;
}
-====================================================
IN c++
#include <bits/stdc++.h>
using namespace std;
#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(ll ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(ll ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
#define pii pair < ll ,ll >
typedef long long ll;
#define hash asdasd
const int inf = 1e9;
const ll mod = 1e9+7;
const ll mod2 = 1e9+7;
const int N = 2e5+5;
const int logN = 18;
ll F[N], i, j, k, n, m, sorted[N], suff[N], lcp[N], ans, hash[N], hash2[N], p, P[N];
string str, str2;
vector< pii > v[N], q[N], v2[N], q2[N];
pair< pii , ll > C[N];
void update(ll x,ll y){
x--;
for(; x > 0 ; x -= x&-x) F[x]--;
for(; y > 0 ; y -= y&-y) F[y]++;
}
ll query(ll x){
ll sum = 0;
for(; x < N ; x += x&-x) sum += F[x];
return sum;
}
ll take(ll x,ll y){ return (hash[y] - ((ll)P[y-x+1] * hash[x-1] % mod)+mod)%mod; }
ll take2(ll x,ll y){ return (hash2[x] - ((ll)P[y-x+1] * hash2[y+1] % mod)+mod)%mod; }
void solve(ll x,ll y){
int bas = 0, son = x;
while(bas < son){
int orta = bas + son >> 1;
if(bas == orta) orta++;
if(take(x-orta+1,x) == take2(y,y+orta-1)) bas = orta;
else son = orta - 1;
}
if(x == y) v[y].pb(mp(x-bas+1,x));
else v2[y].pb(mp(x-bas+1,x));
}
int main(){
cin >> str;
n = str.size(); str = '0' + str;
FOR(i,1,n) suff[i] = str[i];
FOR(j,1,logN){
FOR(i,1,n) C[i] = mp(mp(suff[i],suff[min(n+1,i+(1ll<<j-1))]),i);
sort(C+1,C+n+1);
FOR(i,1,n) suff[C[i].nd] = suff[C[i-1].nd] + (C[i].st != C[i-1].st);
}
FOR(i,1,n) sorted[suff[i]] = i;
int j = 0;
FOR(i,1,n){
if(suff[i] == 1) continue ;
while(i + j <= n && sorted[suff[i]-1] + j <= n && str[sorted[suff[i]-1]+j] == str[i+j]) j++;
if(j%2) q[i+j/2].pb(mp(i,suff[i]-1));
else q2[i+j/2].pb(mp(i,suff[i]-1));
if(j) j--;
}
P[0] = 1;
p = 8;
FOR(i,1,n) P[i] = (P[i-1] * p) % mod;
FOR(i,1,n) hash[i] = (((ll)hash[i-1] * p + (str[i] - 'a'))) % mod;
ROF(i,n,1) hash2[i] = (((ll)hash2[i+1] * p + (str[i] - 'a'))) % mod;
FOR(i,1,n){
if(i != n && str[i] == str[i+1]) solve(i,i+1);
solve(i,i);
}
FOR(i,1,n){
foreach(it,v2[i]) update(it->st,it->nd);
foreach(it,q2[i]) lcp[it->nd] = query(it->st);
foreach(it,v[i]) update(it->st,it->nd);
foreach(it,q[i]) lcp[it->nd] = query(it->st);
}
stack< pii > S;
FOR(i,1,n+1){
// cout << i << ' ' << lcp[i] << endl;
ll index = i;
while(!S.empty() && S.top().st >= lcp[i]){
pii temp = S.top(); S.pop();
index = temp.nd;
ll mx = lcp[i];
if(!S.empty()) mx = max(mx, S.top().st);
ans = (ans + ((temp.st - mx) * (i-temp.nd) * (i-temp.nd+1) / 2)) % mod2;
}
S.push(mp(lcp[i],index));
}
cout << ans << endl;
return 0;
}
==============================================================
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int read_int() {
int ret;
scanf("%d", &ret);
return ret;
}
/* caller should free the memory */
static int *read_int_array(int n) {
int *ret = malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
scanf("%d", ret + i);
}
return ret;
}
static int intcomp(const void *v1, const void *v2) {
return *(const int *)v1 - *(const int *)v2;
}
#define BASE 801
static char powers[BASE][250];
static int power_nums[801];
static void build_powers() {
powers[0][0] = '1';
powers[0][1] = '\0';
power_nums[0] = 1;
for (int i = 1; i <= 800; ++i) {
int previous = power_nums[i - 1];
char *ppower = powers[i - 1];
int start_pos = previous;
if (ppower[0] >= '5') {
start_pos ++;
}
power_nums[i] = start_pos;
char *current = powers[i];
current[start_pos] = '\0';
int rem = 0;
for (int j = previous - 1; j >= 0; --j) {
int val = (ppower[j] - '0') * 2 + rem;
rem = val / 10;
current[start_pos - 1] = '0' + (val % 10);
start_pos --;
}
if (rem != 0) {
/* assert(start_pos == 1); */
current[0] = '0' + rem;
}
}
}
struct node {
struct node *childs;
char child_count;
char c;
/* -3 not initialized
* -2 invalid
* -1 root
* 0 normal
* 1 end!
*/
char end;
};
static void init_node(struct node *n, char c, char end) {
/* n->childs = malloc(10 * sizeof(struct node)); */
/* n->child_count = 10; */
/* for (int i = 0; i < 10; ++i) { */
/* n->c = '0' + i; */
/* n->childs[i].end = -3; */
/* } */
n->c = c;
n->end = end;
}
static struct node *build_node() {
struct node * root = malloc(sizeof(struct node));
init_node(root, 0, -1);
for (int i = 0; i < BASE; ++i) {
struct node *n = root;
for (const char *iter = powers[i]; *iter; iter++) {
/* struct node *child = n[*iter - '0']; */
if (!n->childs) {
/* n = malloc(sizeof(struct node)); */
/* init_node(child, ) */
n->childs = malloc(10 * sizeof(struct node));
n->child_count = 10;
for (int i = 0; i < 10; ++i) {
n->childs[i].c = '0' + i;
/* n->childs[i].end = -3; */
}
}
n = n->childs + (*iter - '0');
}
n->end = 1;
}
return root;
}
static long long int count_appearance(const char *haystack, const char *needle) {
long long int result = 0;
while (1) {
if ((haystack = strstr(haystack, needle))) {
result ++;
haystack++;
} else {
return result;
}
}
}
static long long int solve(const char *buffer, struct node *root) {
/* int len = strlen(buffer); */
/* long long int result = 0; */
/* for (int i = 0; i < BASE && power_nums[i] <= len; ++i) { */
/* result += count_appearance(buffer, powers[i]); */
/* /\* printf("result: %lld\n", result); *\/ */
/* } */
/* return result; */
long long result = 0;
for (const char *iter = buffer; *iter; ++iter) {
/* printf("ITER: %c\n", *iter); */
struct node *n = root;
for (const char *iter2 = iter; *iter2; ++iter2) {
/* printf("ITER2: %c end %d\n", *iter2, n->end); */
if (!n->childs) {
/* previous is the end */
break;
} else {
n = &n->childs[*iter2 - '0'];
if (n->end) {
result++;
}
}
}
}
return result;
}
int main(int argc, char *argv[]) {
build_powers();
struct node *root = build_node();
/* struct node *n = &(root->childs[1]); */
/* printf("%d %c %d ccount: %d\n", n->c, n->c, n->end, n->child_count); */
int t = read_int();
char buffer[100001];
for (int i = 0; i < t; ++i) {
scanf(" %s", buffer);
printf("%lld\n", solve(buffer, root));
}
return 0;
}
