Hacker rank test-25 solutions
Test-25 solutions
1)
#include <math.h>
#include <stdio.h>
#define READNUM 9
double one_twochar(char input2[READNUM]){
return(0.0);
}
double threechar(char input2[READNUM]){
if(input2[0]==input2[2]){
return(0.0);
}
else{
return(3.0);
}
}
double fourchar(char input2[READNUM]){
if(input2[0]==input2[3]){
return(0.0);
}
else{
return(3.0);
}
}
double five_aabbc(char input2[READNUM],char center){
char chartemp;
int i;
if(input2[2]==center){
return (15.6250);
}
else{
for(i=0;i<5;i+=1){
if(input2[i]==center){
input2[i]=input2[2];
input2[2]=center;
}
}
if((input2[0]==input2[4])&&(input2[1]==input2[3])){
return(19.375);
}
else{
return(20.9375);
}
}
}
double five_aaabb(char input2[READNUM],char center){
char chartemp;
int i;
if(input2[2]==center){
return (6.25);
}
else{
return (7.5);
}
}
double fivechar(char input2[READNUM]){
int i,j;
int num=5;
char inputtemp[6],chartemp;
if((input2[0]==input2[4])&&(input2[1]==input2[3])){
return(0.0);
}
else{
for(i=0;i<=num;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<num-1;i+=1){
for(j=i+1;j<num;j+=1){
if(inputtemp[i]>inputtemp[j]){
chartemp=inputtemp[j];
inputtemp[j]=inputtemp[i];
inputtemp[i]=chartemp;
}
}
}
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[4])){
if(inputtemp[0]!=inputtemp[1]){
chartemp=inputtemp[0];
}
else if (inputtemp[2]!=inputtemp[3]){
chartemp=inputtemp[2];
}
else{
chartemp=inputtemp[4];
}
return (five_aabbc(input2,chartemp));
}
else if(inputtemp[1]!=inputtemp[3]){
chartemp=inputtemp[2];
return (five_aaabb(input2,chartemp));
}
else{
chartemp=inputtemp[2];
return (10.0);
}
return(-2.0);
}
}
double sixchar(char input2[READNUM]){
int i,j;
int num=6;
char inputtemp[7],chartemp;
if((input2[0]==input2[5])&&(input2[1]==input2[4])){
return(0.0);
}
else{
for(i=0;i<=num;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<num-1;i+=1){
for(j=i+1;j<num;j+=1){
if(inputtemp[i]>inputtemp[j]){
chartemp=inputtemp[j];
inputtemp[j]=inputtemp[i];
inputtemp[i]=chartemp;
}
}
}
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[4])){
if ((input2[0]==input2[5])||(input2[1]==input2[4])||(input2[2]==input2[3])){
return(17.5);
}
else{
return(20.0);
}
}
else{
return (7.5);
}
return(-2.0);
}
}
double seven_aabbccd(char input2[READNUM],char center){
char chartemp,inputtemp[8];
int i;
if(input2[3]==center){
if((input2[0]==input2[6])||(input2[1]==input2[5])||(input2[2]==input2[4])){
return (117.1793);
}
else{
return (129.3674);
}
}
else{
for(i=0;i<8;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<7;i+=1){
if(inputtemp[i]==center){
inputtemp[i]=inputtemp[3];
inputtemp[3]=center;
}
}
if((inputtemp[0]==inputtemp[6])&&(inputtemp[1]==inputtemp[5])&&(inputtemp[2]==inputtemp[4])){
return(129.6414);
}
else if((inputtemp[0]==inputtemp[6])||(inputtemp[1]==inputtemp[5])||(inputtemp[2]==inputtemp[4])){
if((input2[0]==input2[6])||(input2[1]==input2[5])||(input2[2]==input2[4])){
return(136.2614);
}
else{
return(136.9419);
}
}
else
{
return(138.0556);
}
}
}
double seven_aaabbcc(char input2[READNUM],char center){
char chartemp,inputtemp[8];
int i;
if(input2[3]==center){
if(((input2[0]==input2[6])&&(input2[0]==center))||((input2[1]==input2[5])&&(input2[1]==center))||((input2[2]==input2[4])&&(input2[2]==center))){
return (43.9268);
}
else if(((input2[0]==input2[6])&&(input2[0]!=center))||((input2[1]==input2[5])&&(input2[1]!=center))||((input2[2]==input2[4])&&(input2[2]!=center))){
return (43.4731);
}
else{
return (48.7319);
}
}
else{
for(i=0;i<8;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<7;i+=1){
if((inputtemp[i]==center)&&(inputtemp[i]!=inputtemp[6-i])){
inputtemp[i]=inputtemp[3];
inputtemp[3]=center;
}
}
if((inputtemp[0]==inputtemp[6])&&(inputtemp[1]==inputtemp[5])&&(inputtemp[2]==inputtemp[4])){
return(47.6271);
}
else if((input2[0]==input2[6])||(input2[1]==input2[5])||(input2[2]==input2[4])){
return(51.0299);
}
else{
return(51.2567);
}
}
}
double seven_aaaabbc(char input2[READNUM],char center,char four){
char chartemp,inputtemp[8];
int i,cposi;
if(input2[3]==center){
return (47.1852);
}
else if(input2[3]==four){
if(((input2[0]==input2[6])&&(input2[0]!=center)&&(input2[0]!=four))||((input2[1]==input2[5])&&(input2[1]!=center)&&(input2[1]!=four))
||((input2[2]==input2[4])&&(input2[2]!=center)&&(input2[2]!=four))){
return (55.9352);
}
else{
for(i=0;i<7;i+=1){
if(input2[i]==center){
cposi=i;
}
}
if(input2[6-cposi]==four){
return (59.5648);
}
else{
return (59.3380);
}
}
}
else{
for(i=0;i<8;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<7;i+=1){
if(inputtemp[i]==center){
inputtemp[i]=inputtemp[3];
inputtemp[3]=center;
}
}
if((inputtemp[0]==inputtemp[6])&&(inputtemp[1]==inputtemp[5])&&(inputtemp[2]==inputtemp[4])){
return(56.3889);
}
else
{
return(59.3380);
}
}
}
double seven_aaaabbb(char input2[READNUM],char center){
char chartemp,inputtemp[8];
int i,cposi;
if(input2[3]==center){
return (17.6944);
}
else if(((input2[0]==input2[6])&&(input2[0]==center))||((input2[1]==input2[5])&&(input2[1]==center))||((input2[2]==input2[4])&&(input2[2]==center))){
return (20.6111);
}
else{
return (21.9722);
}
}
double seven_aaaaabb(char input2[READNUM],char center){
char chartemp,inputtemp[8];
int i,cposi;
if(input2[3]==center){
return (12.25);
}
else{
return (14.0);
}
}
double sevenchar(char input2[READNUM]){
int i,j;
int num=7;
char inputtemp[8],chartemp,chartemp2='0';
if((input2[0]==input2[6])&&(input2[1]==input2[5])&&(input2[2]==input2[4])){
return(0.0);
}
else{
for(i=0;i<=num;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<num-1;i+=1){
for(j=i+1;j<num;j+=1){
if(inputtemp[i]>inputtemp[j]){
chartemp=inputtemp[j];
inputtemp[j]=inputtemp[i];
inputtemp[i]=chartemp;
}
}
}
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[4])&&(inputtemp[4]!=inputtemp[6])){
if(inputtemp[0]!=inputtemp[1]){
chartemp=inputtemp[0];
}
else if (inputtemp[2]!=inputtemp[3]){
chartemp=inputtemp[2];
}
else if (inputtemp[4]!=inputtemp[5]){
chartemp=inputtemp[4];
}
else{
chartemp=inputtemp[6];
}
return (seven_aabbccd(input2,chartemp));
}
else if((inputtemp[0]!=inputtemp[3])&&(inputtemp[3]!=inputtemp[6])){
if(inputtemp[0]==inputtemp[2]){
chartemp=inputtemp[0];
return (seven_aaabbcc(input2,chartemp));
}
else if (inputtemp[4]==inputtemp[6]){
chartemp=inputtemp[6];
return (seven_aaabbcc(input2,chartemp));
}
else if (inputtemp[1]==inputtemp[3]){
chartemp=inputtemp[0];
chartemp2=inputtemp[3];
return (seven_aaaabbc(input2,chartemp,chartemp2));
}
else if (inputtemp[3]==inputtemp[5]){
chartemp=inputtemp[6];
chartemp2=inputtemp[3];
return (seven_aaaabbc(input2,chartemp,chartemp2));
}
else{
chartemp=inputtemp[3];
return (seven_aaabbcc(input2,chartemp));
}
return (-4.0);
}
else if((inputtemp[0]==inputtemp[3])&&(inputtemp[3]!=inputtemp[4])&&(inputtemp[4]!=inputtemp[6])){
chartemp2=inputtemp[3];
if(inputtemp[4]==inputtemp[5]){
chartemp=inputtemp[6];
}
else{
chartemp=inputtemp[4];
}
return (seven_aaaabbc(input2,chartemp,chartemp2));
}
else if((inputtemp[6]==inputtemp[3])&&(inputtemp[3]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[0])){
chartemp2=inputtemp[3];
if(inputtemp[2]==inputtemp[1]){
chartemp=inputtemp[0];
}
else{
chartemp=inputtemp[2];
}
return (seven_aaaabbc(input2,chartemp,chartemp2));
}
else if((inputtemp[0]==inputtemp[3])&&(inputtemp[3]!=inputtemp[4])&&(inputtemp[4]==inputtemp[6])){
chartemp=inputtemp[4];
return (seven_aaaabbb(input2,chartemp));
}
else if((inputtemp[0]==inputtemp[2])&&(inputtemp[2]!=inputtemp[3])&&(inputtemp[3]==inputtemp[6])){
chartemp=inputtemp[2];
return (seven_aaaabbb(input2,chartemp));
}
else if((inputtemp[0]==inputtemp[4])&&(inputtemp[4]!=inputtemp[5])&&(inputtemp[5]==inputtemp[6])){
chartemp=inputtemp[4];
return (seven_aaaaabb(input2,chartemp));
}
else if((inputtemp[0]==inputtemp[1])&&(inputtemp[1]!=inputtemp[2])&&(inputtemp[2]==inputtemp[6])){
chartemp=inputtemp[2];
return (seven_aaaaabb(input2,chartemp));
}
else if((inputtemp[0]==inputtemp[5])||(inputtemp[1]==inputtemp[6])){
return (21.0);
}
return(-2.0);
}
}
double eight_aabbccdd(char input2[READNUM]){
char chartemp,inputtemp[8];
int i,count;
count=0;
for(i=0;i<=3;i+=1){
if(input2[i]==input2[7-i]){
count=count+1;
}
}
if(count==2){
return(121.3333);
}
else if (count==1){
return(131.7436);
}
else{
for(i=1;i<=6;i+=1){
if(input2[i]==input2[0]){
count=i;
}
}
if(input2[7-count]==input2[7]){
return(133.3590);
}
else{
return(134.6154);
}
}
}
double eight_aaaabbcc(char input2[READNUM],char four){
char chartemp,inputtemp[8];
int i,count,count2;
count=0;count2=0;
for(i=0;i<=3;i+=1){
if(input2[i]==input2[7-i]){
count=count+1;
if(input2[i]==four){
count2=count2+1;
}
}
}
if((count==2)&&(count2==2)){
return(48.4615);
}
else if ((count==2)&&(count2==1)){
return(47.3846);
}
else if (count==1){
return(52.7692);
}
else{
return(53.3077);
}
}
double eight_aaaabbbb(char input2[READNUM]){
char chartemp,inputtemp[8];
int i,count,count2;
count=0;count2;
for(i=0;i<=3;i+=1){
if(input2[i]==input2[7-i]){
count=count+1;
}
}
if(count==0){
return(21.0);
}
else{
return(18.6667);
}
}
double eightchar(char input2[READNUM]){
int i,j,count,count2;
int num=8;
char inputtemp[9],chartemp;
if((input2[0]==input2[7])&&(input2[1]==input2[6])&&(input2[2]==input2[5])){
return(0.0);
}
else{
for(i=0;i<=num;i+=1){
inputtemp[i]=input2[i];
}
for(i=0;i<num-1;i+=1){
for(j=i+1;j<num;j+=1){
if(inputtemp[i]>inputtemp[j]){
chartemp=inputtemp[j];
inputtemp[j]=inputtemp[i];
inputtemp[i]=chartemp;
}
}
}
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[4])&&(inputtemp[4]!=inputtemp[6])){
return (eight_aabbccdd(input2));
}
else{
count=0;
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[2]!=inputtemp[4])){
count=1;
chartemp=inputtemp[4];
}
if((inputtemp[0]!=inputtemp[2])&&(inputtemp[4]!=inputtemp[6])){
count=1;
chartemp=inputtemp[2];
}
if((inputtemp[2]!=inputtemp[4])&&(inputtemp[4]!=inputtemp[6])){
count=1;
chartemp=inputtemp[0];
}
if(count==1){
return (eight_aaaabbcc(input2,chartemp));
}
else if(inputtemp[2]!=inputtemp[4]){
return(eight_aaaabbbb(input2));
}
else{
return(14.0);
}
}
}
return(-2.0);
}
main(){
int i,j,n;
int length;
double answer;
char input[READNUM];
char filename[100];
// FILE *fp;
// sprintf(filename,"input01.txt");
// fp=fopen(filename,"r");
// fscanf(fp,"%d", &n);
scanf("%d", &n);
for(i=0;i<n;i+=1){
answer=-1.0;
scanf("%s", input);
// fscanf(fp,"%s", input);
length=0;
for(j=8;j>=1;j-=1){
if(input[j]=='\0'){
length=j;
}
}
if(length<=2){
answer=one_twochar(input);
}
else if(length==3){
answer=threechar(input);
}
else if(length==4){
answer=fourchar(input);
}
else if(length==5){
answer=fivechar(input);
}
else if(length==6){
answer=sixchar(input);
}
else if(length==7){
answer=sevenchar(input);
}
else if(length==8){
answer=eightchar(input);
}
printf("%.4f\n",answer);
}
// fclose(fp);
}
2) We Will Come Back Soon With 2 problem
3)
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> int main() { int n; scanf("%d", &n); int *dc = calloc(n, sizeof(int)); int count = 0; for (int i = 0; i < n; i++) { int x; scanf("%d", &x); if (x < n) { int start = (i+1)%n; int end = (start-x+n)%n; dc[start]++; dc[end]--; if (end <= start) count++; } } int id = 0; int val = 0; for (int i = 0; i < n; i++) { count += dc[i]; if (count > val) { val = count; id = i; } } printf("%d", id+1); free(dc); return 0; }
Test-24 Solution
LINK: https://www.hackerrank.com/contests/codingtest-24
1)
1)
#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;
}
2) C++
#include <stdio.h>
#include <set>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define L 5000011
int sa[L];
int sai[L];
int lcp[L];
int v[L];
char s[L];
ll ts[L];
int p[L<<1];
char t[L<<1];
int m, n;
set<ll> found;
bool scomp(int i, int j) {
return s[i] < s[j];
}
bool tscomp(int i, int j) {
return ts[i] < ts[j];
}
void get_suffix_array() {
for (int i = 0; i < n; i++) v[i] = i;
sort(v, v + n, scomp);
sai[v[0]] = 1;
for (int i = 1; i < n; i++) {
if (s[v[i]] == s[v[i - 1]]) {
sai[v[i]] = sai[v[i - 1]];
} else {
sai[v[i]] = i+1;
}
}
for (int p = 1; p <= n; p <<= 1) {
for (int i = 0; i < n-p; i++) ts[i] = sai[i] * (n+1LL) + sai[i+p];
for (int i = n-p; i < n; i++) ts[i] = sai[i] * (n+1LL);
sort(v, v + n, tscomp);
sai[v[0]] = 1;
for (int i = 1; i < n; i++) {
if (ts[v[i]] == ts[v[i - 1]]) {
sai[v[i]] = sai[v[i - 1]];
} else {
sai[v[i]] = i+1;
}
}
}
for (int i = 0; i < n; i++) sai[i]--;
for (int i = 0; i < n; i++) sa[sai[i]] = i;
}
void get_lcp() {
for (int i = 0; i < n; i++) lcp[i] = 0;
int l = 0;
for (int i = 0; i < n-1; i++) {
int k = sai[i];
int j = k ? sa[k-1] : sa[n-1];
while (j + l < n and s[i + l] == s[j + l]) {
l++;
}
lcp[k] = l;
if (l > 0) {
l--;
}
}
}
void manacher() {
// from wikipedia
// t has been processed
int center = 0, end = 0, left = 0, right = 0;
for (int i = 1; i < m; i++) {
if (i > end) {
p[i] = 0;
left = i - 1;
right = i + 1;
} else {
int j = 2*center - i; // index on the other side
if (p[j] < end - i) { // whole palindrome is inside
p[i] = p[j];
left = -1; // so we don't enter the loop below
} else {
p[i] = end - i;
right = end + 1;
left = 2*i - right;
}
}
while (left >= 0 and right < m and t[left] == t[right]) {
p[i]++;
left--;
right++;
}
if (i + p[i] > end) {
center = i;
end = i + p[i];
}
}
}
struct Node {
int i, j, v;
Node *p, *l, *r;
Node(int i, int j, Node *p = NULL): i(i), j(j), p(p) {
if (j - i == 1) {
l = r = NULL;
v = lcp[i];
} else {
int k = i + j >> 1;
l = new Node(i, k, this);
r = new Node(k, j, this);
v = min(l->v, r->v);
}
}
};
int node_minocc(Node *node, int v, int i) {
// find maximum j, 0 <= j <= i such that a[j] < v
while (node->l) {
if (i < node->l->j) {
node = node->l;
} else {
node = node->r;
}
}
// now node->i = i < node->j = i+1
if (node->v < v) {
return node->i;
}
while (true) {
while (node->p and node->p->l == node) {
node = node->p;
}
if (!node->p) {
return 0;
}
node = node->p;
if (node->l->v < v) {
node = node->l;
break;
}
}
while (node->l) {
if (node->r->v < v) {
node = node->r;
} else {
node = node->l;
}
}
return node->i;
}
int node_maxocc(Node *node, int v, int i) {
// find maximum j, i <= j <= n such that a[j] >= v
if (i == n) {
return n;
}
while (node->l) {
if (i < node->l->j) {
node = node->l;
} else {
node = node->r;
}
}
// now node->i = i < node->j = i+1
if (node->v < v) {
return node->i;
}
while (true) {
while (node->p and node->p->r == node) {
node = node->p;
}
if (!node->p) {
return n;
}
node = node->p;
if (node->r->v < v) {
node = node->r;
break;
}
}
while (node->l) {
if (node->l->v < v) {
node = node->l;
} else {
node = node->r;
}
}
return node->i;
}
int main() {
scanf("%s", s);
n = strlen(s);
// suffix tree
get_suffix_array();
get_lcp();
Node *root = new Node(0, n);
m = 0;
for (int i = 0; i < n; i++) {
t[m++] = '#';
t[m++] = s[i];
}
t[m++] = '$';
t[0] = '^';
manacher();
ll ans = 0;
for (int i = 1; i < m-1; i++) {
int k = p[i];
if (t[i-k] == '#') k--;
for(; k >= 0; k -= 2) {
int start = sai[i-k>>1];
int mino = node_minocc(root,k+1,start);
ll hsh = k*(n+1LL)+mino;
if (found.find(hsh) != found.end()) {
break;
}
found.insert(hsh);
int maxo = node_maxocc(root,k+1,start+1);
ll c = maxo - mino;
ans += c*(c-1);
ans %= mod;
}
}
ans = ans * (mod+1>>1) % mod;
printf("%lld\n", ans);
}
3)
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static int read_int() {
int ret;
scanf("%d", &ret);
return ret;
}
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) {
current[0] = '0' + rem;
}
}
}
struct node {
struct node *childs;
char child_count;
char c;
char end;
};
static void init_node(struct node *n, char c, char end) {
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++) {
if (!n->childs) {
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 = 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) {
long long result = 0;
for (const char *iter = buffer; *iter; ++iter) {
struct node *n = root;
for (const char *iter2 = iter; *iter2; ++iter2) {
if (!n->childs) {
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();
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;
}
Test-23 Solution
Link: https://www.hackerrank.com/ece-test-23
1)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(char *str,int *a);
void init( int n );
void range_increment( int i, int j, int val );
int query( int i );
int max(int x,int y);
void update(int x,int y,int z);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
char str[1000001]={0};
int N,NN,a[2000004],tree[2000000],ans[500000],b[500000],c[500000];
int main(){
int i,j;
scanf("%d%s",&NN,str);
strncpy(str+NN,str,NN);
solve(str,a);
init(NN);
for(i=0;i<4*NN;i++)
if(a[i])
if(i%2)
update(i/2-a[i]/2,i/2+a[i]/2,a[i]);
else
update(i/2-a[i]/2,i/2+a[i]/2-1,a[i]);
for(i=0;i<NN;i++){
ans[i]=query(i);
b[i]=ans[i];
c[i]=i;
}
sort_a2(b,c,NN);
for(i=NN;i>=0;i--){
for(j=c[i];1;j=(j-1+NN)%NN)
if(ans[j]-ans[(j-1+NN)%NN]>2)
ans[(j-1+NN)%NN]=ans[j]-2;
else
break;
for(j=c[i];1;j=(j+1)%NN)
if(ans[j]-ans[(j+1)%NN]>2)
ans[(j+1)%NN]=ans[j]-2;
else
break;
}
for(i=0;i<NN;i++)
printf("%d\n",ans[i]);
return 0;
}
void solve(char *str,int *a){
char *p;
int len,R,Ri,i,j,mi;
len=strlen(str);
p=(char*)malloc(2*(len+1)*sizeof(char));
for(i=0;i<len;i++){
p[2*i]='#';
p[2*i+1]=str[i];
}
p[2*i]='#';
p[2*i+1]=0;
a[0]=R=Ri=0;
for(i=1;i<=len*2;i++)
if(i>=R){
if(p[i]!='#')
a[i]=1;
else
a[i]=0;
for(j=i+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else{
mi=2*Ri-i;
if(i+a[mi]>=R || mi==a[mi]){
a[i]=R-i;
for(j=R+1;1;j++)
if(j<=2*len && 2*i-j>=0 && p[j]==p[2*i-j]){
if(p[j]!='#')
a[i]+=2;
}
else{
Ri=i;
R=j-1;
break;
}
}
else
a[i]=a[mi];
}
free(p);
return;
}
void init( int n ){
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
void range_increment( int i, int j, int val ){
for( i += N, j += N; i <= j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] = max(tree[i],val);
if( j % 2 == 0 ) tree[j] = max(tree[j],val);
}
}
int query( int i ){
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans = max(ans,tree[j]);
return ans;
}
int max(int x,int y){
return (x>y)?x:y;
}
void update(int x,int y,int z){
if(z>NN){
int m=x+z/2;
if(z%2)
if(NN%2)
update(m-NN/2,m+NN/2,NN);
else
update(m-NN/2+1,m+NN/2-1,NN-1);
else
if(NN%2)
update(m-NN/2,m+NN/2-1,NN-1);
else
update(m-NN/2,m+NN/2-1,NN);
}
if(y<NN){
range_increment(0,x,z);
range_increment(y+1,NN-1,z);
}
else
range_increment(y-NN+1,x,z);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
2)C++
#include<bits/stdc++.h> #include<iostream> using namespace std; #define fre freopen("in.txt","r",stdin);//freopen("0.out","w",stdout) #define abs(x) ((x)>0?(x):-(x)) #define MOD 1000000007 #define LL signed long long int #define scan(x) scanf("%d",&x) #define print(x) printf("%d\n",x) #define scanll(x) scanf("%lld",&x) #define printll(x) printf("%lld\n",x) #define rep(i,from,to) for(int i=(from);i <= (to); ++i) #define pii pair<int,int> vector<int> G[2*100000+5]; int mp[11]; LL p10[50000+5]; LL Hash[11][50000+5]; int num[50000+5][11]; int N; LL get(int n,int i,int j){ return (Hash[n][j] + MOD - Hash[n][i-1] * p10[j-i+1]%MOD)%MOD; } LL getHash(int i,int j){ LL ans = 0; for(int x=1;x<=10;++x){ if(num[i][x] != N) ans = ans + get(x,i,j) * num[i][x]; } return ans; } int bin(int i,int j,int s1,int s2){ if(i==j)return i; int L = ceil((i+j)/2.0); if(getHash(s1,s1+L-1)==getHash(s2,s2+L-1)) return bin(L,j,s1,s2); return bin(i,L-1,s1,s2); } string S; int calcLCP(int i,int j){ if(i>j)swap(i,j); return bin(1,min(N-j+1,N-i+1),i,j); } bool compare(int i,int j){ int mx = calcLCP(i,j); if(max(i+mx-1,j+mx-1)==N)return i>j; return num[i][S[i+mx]-'a'+1] < num[j][S[j+mx]-'a'+1]; } int SA[50000+5]; int lcp[50000+5]; template<typename T> class range_minimum_query{ public: std::vector<T> data; std::vector<std::vector<int> > block; std::vector<int> sblock; std::vector<int> lookup; int N; int lg; int min(int a,int b){ return data[b]<data[a]?b:a; } range_minimum_query(){} range_minimum_query(std::vector<T> &t){ data=t; N=data.size(); lg=32-__builtin_clz(N); block.assign((N+lg-1)/lg,std::vector<int>(lg,0)); for(int i=0;i<N;i++){ if(i%lg==0) block[i/lg][0]=i; block[i/lg][0]=min(i,block[i/lg][0]); } for(int j=1;j<lg;j++) for(int i=0;i<block.size();i++) block[i][j]=min(block[i][j-1],block[i+(i+(1<<(j-1))<block.size()?(1<<(j-1)):0)][j-1]); sblock.assign(N,0); std::vector<int> st; for(int i=0;i<block.size();i++){ st.clear(); for(int j=i*lg;j<N&&j<i*lg+lg;j++){ while(!st.empty()&&data[j]<data[st.back()]) st.pop_back(); sblock[j]=1<<(i*lg+lg-j-1); if(!st.empty()) sblock[j]|=sblock[st.back()]; st.push_back(j); } } lookup.assign(1<<lg,0); for(int i=1,ans=lg-1;i<(1<<lg);i++){ if(1<<(lg-ans)<=i) ans--; lookup[i]=ans; } } int q(int l,int r){ if(r<l) swap(l,r); int l1=l/lg+1; int r1=r/lg-1; int ans=l; int t; if(l1<=r1){ t=lg-lookup[r1-l1+1]-1; ans=min(ans,min(block[l1][t],block[r1-(1<<t)+1][t])); } t=l1*lg-1<r?l1*lg-1:r; ans=min(ans,lookup[sblock[t]&(~(((1<<(l-(l1*lg-lg)))-1)<<(l1*lg-l)))]+l1*lg-lg); t=r; l=l>r1*lg+lg?l:r1*lg+lg; ans=min(ans,lookup[sblock[t]&(~(((1<<(l-(r1*lg+lg)))-1)<<(r1*lg+(lg<<1)-l)))]+r1*lg+lg); return data[ans]; } }; range_minimum_query<int> *rmq; int bindown(int s,int i,int j,int F){ if(i==j)return i; int m = ceil((i+j)/2.0); if(rmq->q(s+1,m) >= F)return bindown(s,m,j,F); return bindown(s,i,m-1,F); } int binup(int s,int i,int j,int F) { if(i==j) return i; int m = (i+j)/2; if(rmq->q(m+1,s) >= F)return binup(s,i,m,F); return binup(s,m+1,j,F); } int pos[50000+5]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int Q; cin>>N>>Q; cin>>S; S = " "+S; p10[0] = 1; rep(i,1,N)p10[i] = p10[i-1] * 10 % MOD; for(int i=1;i<=10;++i){ Hash[i][0] = 0; for(int j=1;j<=N;++j){ Hash[i][j] = Hash[i][j-1] * 10 + ((S[j]-'a'+1)==i); Hash[i][j] %= MOD; } } int mp[11]; rep(i,1,10)mp[i] = N+1; for(int i=N;i>=1;--i){ vector<int>v; mp[S[i]-'a'+1] = i; for(int j=1;j<=10;++j)v.push_back(mp[j]); sort(v.begin(),v.end()); for(int j=0;j<v.size() and v[j]<=N;++j){ num[i][S[v[j]]-'a'+1] = j+1; } } for(int i=1;i<=N;++i){ SA[i] = i; } sort(SA+1,SA+N+1,compare); rep(i,1,N)pos[SA[i]] = i; vector<int>lcp; lcp.push_back(0);lcp.push_back(0); for(int i=2;i<=N;++i){ lcp.push_back(calcLCP(SA[i],SA[i-1])); } // rep(i,1,N)cout<<SA[i]<<' '<<lcp[i]<<' '<<getHash(SA[i],N)<<endl; rmq = new range_minimum_query<int>(lcp); while(Q--){ int L,R; cin>>L>>R; int len = R-L+1; int p = pos[L]; int d = lcp[p+1] >= len?bindown(p,p+1,N,len):p; int u = lcp[p] >= len?binup(p,1,p-1,len):p; // cout<<p<<' '<<u<<' '<<d<<endl; cout<<d-u+1<<endl; } }3)#include <stdio.h>#include <string.h> #include <stdlib.h> #include <time.h> #define kMaxSize 100001 #define kMaxMismatch 1 typedef long long int lli; int findDna8b(char* p, char* v, int vc); int main() { // Allocate memory for strings. char* p = (char*)malloc(kMaxSize * sizeof(char)); char* v = (char*)malloc(kMaxSize * sizeof(char)); // Test cases. int tc; scanf("%d", &tc); while (0 < tc--) { // Load strings. scanf("%s %s", p, v); int pc = (int)strlen(p); int vc = (int)strlen(v); // Look for v in p. Print starting index of each match. int c = (pc-vc); int matched = 0; for (int i = 0; i <= c; i++){ if (findDna8b(&p[i], v, vc) == 1){ matched++; printf("%d ", i); } } // We have to indicate if no matches were found. if (matched <= 0) printf("No Match!\n"); else printf("\n"); } return 0; } int findDna8b(char* p, char* v, int vc) { lli* p8 = (lli*)p; lli* v8 = (lli*)v; int c = vc/8; int mismatch = 0; int i; for (i = 0; i < c; i++){ if (p8[i] != v8[i]) { for (int j = i*8; j < (i*8)+8; j++){ if (p[j] != v[j]){ mismatch++; if (mismatch > kMaxMismatch) return -1; } } } } for (int j = i*8; j < vc; j++){ if (p[j] != v[j]){ mismatch++; if (mismatch > kMaxMismatch) return -1; } } return 1; }
1)
#include<stdio.h>
#include<string.h>
#define maxn 100100
int wa[maxn],wb[maxn],wv[maxn],ws[maxn];
int r[maxn],sa[maxn];
char str[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[x[i]=r[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
for(j=1,p=1;p<n;j*=2,m=p)
{
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=0;i<n;i++) wv[i]=x[y[i]];
for(i=0;i<m;i++) ws[i]=0;
for(i=0;i<n;i++) ws[wv[i]]++;
for(i=1;i<m;i++) ws[i]+=ws[i-1];
for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
return;
}
int Rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for(i=1;i<=n;i++) Rank[sa[i]]=i;
for(i=0;i<n;height[Rank[i++]]=k)
for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
return;
}
int main()
{
int cas;
long long k;
scanf("%d",&cas);
while(cas--)
{
int i,j;
scanf("%s",str);
scanf("%lld",&k);
int len=strlen(str);
for(i=0;i<len;i++) r[i]=str[i];
r[len]=0;
da(r,sa,len+1,130);
calheight(r,sa,len);
long long sum=0;
long long L,R,tot;
for(i=1;i<=len;i++)
{
R=len-sa[i];
L=height[i]+1;
tot=(L+R)*(R-L+1)/2;
if(sum+tot<k) sum+=tot;
else
{
for(j=1;j<=R-L+1;j++)
{
if(sum+L+j-1<k) sum=sum+(L+j-1);
else
{
int pos=k-sum-1+sa[i];
printf("%c\n",str[pos]);
break;
}
}
break;
}
}
}
return 0;
}
2)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#define min(a, b) ((a) > (b) ? (b) : (a))
#define MAX_STR_LEN 110000
char input[MAX_STR_LEN];
int table[MAX_STR_LEN];
int fill_table_and_return_sum_of_common_prefixes(char *str) {
int strlength = strlen(str), i = 2, j = 0, sum = strlength;
table[0] = -1;
table[1] = 0;
while (i < strlength) {
if (str[i - 1] == str[j]) {
j++;
table[i] = j;
i++;
} else if (j > 0){
j = table[j];
} else {
table[i] = 0;
i++;
}
}
for (i = 1; i < strlength; i++) {
printf("%d, ", table[i]);
if(table[i] < table[i - 1]) { sum += table[i - 1]; }
}
sum += table[i - 1];
printf("\n");
return sum;
}
char *reverse(char *str) {
int len = strlen(str), i;
char c;
for(i = 0; i < (len / 2); i++) {
c = str[i];
str[i] = str[len - i - 1];
str[len - i - 1] = c;
}
return str;
}
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;
}
long long z_algo(char *str) {
int i, L = 0, R = 0, strlength = strlen(str);
long long sum = strlength;
table[0] = 0;
for (i = 1; i < strlength; i++) {
if (i > R) {
L = R = i;
while (R < strlength && str[R-L] == str[R]) R++;
table[i] = R-L; R--;
} else {
int k = i-L;
if (table[k] < R-i+1) table[i] = table[k];
else {
L = i;
while (R < strlength && str[R-L] == str[R]) R++;
table[i] = R-L; R--;
}
}
}
for (i = 1; i < strlength; i++) {
sum += table[i];
}
return sum;
}
int main(int argc, char **argv) {
int num_words;
FILE *fp = stdin;
fgets(input, 3000, fp);
num_words = atoi(input);
// printf("%d\n", num_words);
while(num_words > 0) {
num_words--;
fgets(input, MAX_STR_LEN, fp);
// printf("%d\n", strlen(input));
chomp(input);
// printf("%s\n", input);
// printf("%s\n", reverse(input));
printf("%llu\n", z_algo(input));
}
return 0;
}
3)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define A_SIZE 26
#define MIN_C 'a'
#define MOD 1000000007
typedef struct _st_node st_node;
typedef struct _st_edge st_edge;
struct _st_node{
st_node *suffix_link;
st_edge *edges[A_SIZE+1];
};
struct _st_edge{
int from;
int to;
int suffix_index;
st_node *node;
};
void print(st_node *root,int len);
void suffix_tree(st_node *root,char *str,int len);
long long modPow(long long a,int x);
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
char str[100001];
int dp[100000][26];
long long ans,pows[26][100001];
int main(){
int T,len,i,j;
st_node root;
for(i=0;i<26;i++)
for(j=1;j<=100000;j++)
pows[i][j]=(pows[i][j-1]+modPow(j,i+1))%MOD;
scanf("%d",&T);
while(T--){
scanf("%s",str);
len=strlen(str);
for(i=0;i<26;i++)
dp[len-1][i]=-1;
dp[len-1][str[len-1]-MIN_C]=len-1;
for(i=len-2;i>=0;i--){
memcpy(&dp[i][0],&dp[i+1][0],26*sizeof(int));
dp[i][str[i]-MIN_C]=i;
}
suffix_tree(&root,str,len);
ans=0;
print(&root,0);
printf("%lld\n",ans);
}
return 0;
}
void print(st_node *root,int len){
int i,j,idx,from,to,s,dc,last,t,a[26];
if(!root)
return;
for(i=0;i<A_SIZE;i++)
if(root->edges[i]){
idx=root->edges[i]->suffix_index;
from=idx+len;
to=idx+len+root->edges[i]->to-root->edges[i]->from;
s=dc=0;
last=idx+len-1;
for(j=0;j<26;j++)
if(dp[idx][j]!=-1 && dp[idx][j]<from)
dc++;
else if(dp[idx][j]>=from && dp[idx][j]<=to)
a[s++]=dp[idx][j];
sort_a(a,s);
for(j=0;j<s;j++,dc++){
t=a[j]-1;
if(dc)
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
last=t;
}
t=to;
ans=(ans+pows[dc-1][t-idx+1]-pows[dc-1][last-idx+1]+MOD)%MOD;
print(root->edges[i]->node,len+root->edges[i]->to-root->edges[i]->from+1);
}
return;
}
void suffix_tree(st_node *root,char *str,int len){
int a_edge,a_len=0,remainder=0,need_insert,from,i;
st_node *a_node=root,*pre_node,*t_node;
st_edge *t_edge;
memset(root,0,sizeof(st_node));
for(i=0;i<=len;i++){
need_insert=0;
pre_node=NULL;
remainder++;
if(i==len)
need_insert=1;
else if(a_len)
if(str[a_node->edges[a_edge]->from+a_len]==str[i])
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
else
need_insert=1;
else
if(a_node->edges[str[i]-MIN_C])
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
else
need_insert=1;
if(need_insert)
for(;remainder>0;remainder--){
if(!a_len)
if(i==len){
a_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
a_node->edges[A_SIZE]->suffix_index=i-remainder+1;
a_node->edges[A_SIZE]->node=NULL;
}
else{
if(a_node->edges[str[i]-MIN_C]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[str[i]-MIN_C]->from==a_node->edges[str[i]-MIN_C]->to)
a_node=a_node->edges[str[i]-MIN_C]->node;
else{
a_edge=str[i]-MIN_C;
a_len=1;
}
break;
}
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
a_node->edges[str[i]-MIN_C]=t_edge;
t_node=a_node;
}
else{
if(i!=len && str[a_node->edges[a_edge]->from+a_len]==str[i]){
if(pre_node)
pre_node->suffix_link=a_node;
if(a_node->edges[a_edge]->from+a_len==a_node->edges[a_edge]->to){
a_node=a_node->edges[a_edge]->node;
a_len=0;
}
else
a_len++;
break;
}
t_node=(st_node*)malloc(sizeof(st_node));
memset(t_node,0,sizeof(st_node));
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=a_node->edges[a_edge]->from+a_len;
t_edge->to=a_node->edges[a_edge]->to;
t_edge->suffix_index=a_node->edges[a_edge]->suffix_index;
t_edge->node=a_node->edges[a_edge]->node;
from=a_node->edges[a_edge]->from;
a_node->edges[a_edge]->node=t_node;
a_node->edges[a_edge]->to=a_node->edges[a_edge]->from+a_len-1;
t_node->edges[str[t_edge->from]-MIN_C]=t_edge;
if(i==len){
t_node->edges[A_SIZE]=(st_edge*)malloc(sizeof(st_edge));
t_node->edges[A_SIZE]->suffix_index=i-remainder+1;
t_node->edges[A_SIZE]->node=NULL;
}
else{
t_edge=(st_edge*)malloc(sizeof(st_edge));
t_edge->from=i;
t_edge->to=len-1;
t_edge->suffix_index=i-remainder+1;
t_edge->node=NULL;
t_node->edges[str[i]-MIN_C]=t_edge;
}
}
if(pre_node)
pre_node->suffix_link=t_node;
pre_node=t_node;
if(a_node==root && a_len>0){
if(remainder>1)
a_edge=str[i-remainder+2]-MIN_C;
from=i-remainder+2;
a_len--;
}
else if(a_node!=root)
if(a_node->suffix_link)
a_node=a_node->suffix_link;
else
a_node=root;
while(a_len>0 && a_len>=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1){
a_len-=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
from+=a_node->edges[a_edge]->to-a_node->edges[a_edge]->from+1;
a_node=a_node->edges[a_edge]->node;
a_edge=str[from]-MIN_C;
}
}
}
return;
}
long long modPow(long long a,int x){
long long res = 1;
while(x>0){
if(x%2)
res=(res*a)%MOD;
a=(a*a)%MOD;
x>>=1;
}
return res;
}
void sort_a(int*a,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int *left,*right;
left=(int*)malloc(m*sizeof(int));
right=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++)
left[i]=a[i];
for(i=0;i<size-m;i++)
right[i]=a[i+m];
sort_a(left,m);
sort_a(right,size-m);
merge(a,left,right,m,size-m);
free(left);
free(right);
return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right[j];
j++;
} else if (j == right_size) {
a[i+j] = left[i];
i++;
} else if (left[i] <= right[j]) {
a[i+j] = left[i];
i++;
} else {
a[i+j] = right[j];
j++;
}
}
return;
}
TEST -21 solutions
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define L 100001
int checkPal(char *a){
int i,j;
i =0;
j = strlen(a) -1;
while( i <= j){
if(a[i] != a[j])
return 0;
i++; j--;
}
// printf("%s:YEA PALI: LLL:%d\n", a, strlen(a));
return 1;
}
char *findPal(char *a, char *b, char *curr){
char p[L], buf[L];
p[0] = 0;
curr[0] =0;
int i, j, k, m,n;
for(i=0; a[i]; i++)
if(a[i] == '\n')
a[i] =0;
for(i=0; b[i]; i++)
if(b[i] == '\n')
b[i] =0;
for(i=0; a[i]; i++){
for(j=i; a[j]; j++){
p[0] =0;
strncpy(buf, a+i, j -i+1);
buf[j-i+1] =0;
strcat(p, buf);
// printf("%s:B1,,P;%s\n", buf, p);
for(m=0; b[m]; m++)
for(n=m; b[n]; n++){
strncpy(buf, b+m, n -m+1);
int ind = strlen(p);
buf[n -m+1] =0;
strcat(p, buf);
// printf("%s:B2,,,P::%s:::b-Now:%s\n", buf, p, b);
// printf("%s:my p\n", p);
if(checkPal(p) == 1)
if(strlen(p) > strlen(curr))
strcpy(curr, p);
else if(strlen(p) == strlen(curr)){
if(strcmp(p, curr) < 0)
strcpy(curr, p);
}
p[ind] =0;
}
}
}
return curr;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
char s1[L], s2[L], a1[27], a2[27], curr[L], qs[30];
int i, q,k, ok =0;
a1[26] =a2[26]=0;
fgets(qs, 20, stdin);
q= atoi(qs);
for(k =0; k<q; k++){
fgets(s1, L, stdin );
fgets(s2, L, stdin );
for(i=0; i < 26; i++){
a2[i] = '0';
a1[i] = '0';
}
for(i=0; s1[i]; i++)
a1[s1[i]-97] = '1';
for(i=0; s2[i]; i++)
a2[s2[i]-97] = '1';
for(i=0; i < 26; i++)
if(a1[i] == '1' && a2[i] == '1'){
ok = 1;
break;
}
if(ok == 0) {
printf("-1\n");
}
else
printf("%s\n", findPal(s1, s2, curr));
ok = 0;
}
return 0;
}
===========================================2)
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define L 100001
int checkPal(char *a){
int i,j;
i =0;
j = strlen(a) -1;
while( i <= j){
if(a[i] != a[j])
return 0;
i++; j--;
}
// printf("%s:YEA PALI: LLL:%d\n", a, strlen(a));
return 1;
}
char *findPal(char *a, char *b, char *curr){
char p[L], buf[L];
p[0] = 0;
curr[0] =0;
int i, j, k, m,n;
for(i=0; a[i]; i++)
if(a[i] == '\n')
a[i] =0;
for(i=0; b[i]; i++)
if(b[i] == '\n')
b[i] =0;
for(i=0; a[i]; i++){
for(j=i; a[j]; j++){
p[0] =0;
strncpy(buf, a+i, j -i+1);
buf[j-i+1] =0;
strcat(p, buf);
// printf("%s:B1,,P;%s\n", buf, p);
for(m=0; b[m]; m++)
for(n=m; b[n]; n++){
strncpy(buf, b+m, n -m+1);
int ind = strlen(p);
buf[n -m+1] =0;
strcat(p, buf);
// printf("%s:B2,,,P::%s:::b-Now:%s\n", buf, p, b);
// printf("%s:my p\n", p);
if(checkPal(p) == 1)
if(strlen(p) > strlen(curr))
strcpy(curr, p);
else if(strlen(p) == strlen(curr)){
if(strcmp(p, curr) < 0)
strcpy(curr, p);
}
p[ind] =0;
}
}
}
return curr;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
char s1[L], s2[L], a1[27], a2[27], curr[L], qs[30];
int i, q,k, ok =0;
a1[26] =a2[26]=0;
fgets(qs, 20, stdin);
q= atoi(qs);
for(k =0; k<q; k++){
fgets(s1, L, stdin );
fgets(s2, L, stdin );
for(i=0; i < 26; i++){
a2[i] = '0';
a1[i] = '0';
}
for(i=0; s1[i]; i++)
a1[s1[i]-97] = '1';
for(i=0; s2[i]; i++)
a2[s2[i]-97] = '1';
for(i=0; i < 26; i++)
if(a1[i] == '1' && a2[i] == '1'){
ok = 1;
break;
}
if(ok == 0) {
printf("-1\n");
}
else
printf("%s\n", findPal(s1, s2, curr));
ok = 0;
}
return 0;
}
===========================================2)
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int t;
scanf("%d",&t);
while(t--)
{
int c,cou,m,n,l,i,j,k,a,b,sum=0,l1;
scanf("%d %d %d",&l,&a,&b);
char str[l];
scanf("%s",str);
// clrscr();
for(i=0;i<l;i++)
{
k=0;cou=0;
for(j=0;j<i;j++)
{
if(str[i]==str[j])
{
c=0;
for(m=j,n=i;m<i;m++,n++)
{ if(str[m]==str[n])
c++;
else
break;
}
if(cou<c)
{cou=c;k=1;l1=c-1; }
}
}
if(!k)
{//printf("%d-%d\n",i,a);
sum+=a;}
else if(cou*a>b)
{//printf("%d-%d\n",i,b);
sum+=b;
i+=l1;
}
else
{ //printf("%d - %d\n",i,a);
sum+=a;
}
// printf("+");
}
printf("%d\n",sum);}
return 0;
}
3)
#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],bl1[1200],dr1[1200],dl1[1200],ur1[1200],ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],bl2[1200],dr2[1200],dl2[1200],ur2[1200],ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};
int main(){
int T,i,j;
long long t1,t2;
scanf("%d",&T);
while(T--){
hash_count=0;
scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i){
tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
}
else{
tl1[i]=a[0][i]-'a';
bl1[i]=a[1][i]-'a';
tl2[i]=a[0][i]-'a';
bl2[i]=a[1][i]-'a';
}
for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i!=N-1){
tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
}
else{
tr1[N-i-1]=a[0][i]-'a';
br1[N-i-1]=a[1][i]-'a';
tr2[N-i-1]=a[0][i]-'a';
br2[N-i-1]=a[1][i]-'a';
}
for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
}
for(i=0,t1=t2=1;i<N;i++){
if(i%2){
ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
else
if(!i){
ul1[2*i]=a[1][i]-'a';
dl1[2*i]=a[0][i]-'a';
ul2[2*i]=a[1][i]-'a';
dl2[2*i]=a[0][i]-'a';
}
else{
ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if(i%2){
ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
}
else{
ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--)
if(i==N-1){
ur1[2*(N-1-i)]=a[1][i]-'a';
dr1[2*(N-1-i)]=a[0][i]-'a';
ur2[2*(N-1-i)]=a[1][i]-'a';
dr2[2*(N-1-i)]=a[0][i]-'a';
t1=t1*26%MOD1;
t2=t2*26%MOD2;
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
else{
if((N-i)%2==0){
ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
else{
ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if((N-i)%2==0){
ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
else{
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=0;i<=2*N;i++)
if(i){
mod1[i]=mod1[i-1]*26%MOD1;
inmod1[i]=modInverse(mod1[i],MOD1);
mod2[i]=mod2[i-1]*26%MOD2;
inmod2[i]=modInverse(mod2[i],MOD2);
}
else
mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
for(i=0;i<=N;i++)
for(j=i;j<=N;j++)
solve(i,j);
printf("%d\n",hash_count);
freehash();
}
return 0;
}
void solve(int i,int j){
long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
t1=tr1[N+i-1];
t2=br1[N+i-1];
if(i!=N){
t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
t2=(t2-br1[N-i-1]+MOD1)%MOD1;
}
t1=t1*inmod1[N-i]%MOD1;
t2=t2*inmod1[N-i]%MOD1;
t3=tl1[2*N-j-1];
t4=bl1[2*N-j-1];
if(j){
t3=(t3-tl1[j-1]+MOD1)%MOD1;
t4=(t4-bl1[j-1]+MOD1)%MOD1;
}
t3=t3*inmod1[j]%MOD1;
t4=t4*inmod1[j]%MOD1;
if(!j)
t5=t6=0;
else{
t5=ul1[2*j-1];
t6=dl1[2*j-1];
if(i){
t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
}
}
if(i==N)
t7=t8=0;
else{
t7=ur1[2*(N-i)-1];
t8=dr1[2*(N-i)-1];
if(j!=N){
t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
}
}
tt1=tr2[N+i-1];
tt2=br2[N+i-1];
if(i!=N){
tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
}
tt1=tt1*inmod2[N-i]%MOD2;
tt2=tt2*inmod2[N-i]%MOD2;
tt3=tl2[2*N-j-1];
tt4=bl2[2*N-j-1];
if(j){
tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
}
tt3=tt3*inmod2[j]%MOD2;
tt4=tt4*inmod2[j]%MOD2;
if(!j)
tt5=tt6=0;
else{
tt5=ul2[2*j-1];
tt6=dl2[2*j-1];
if(i){
tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
}
}
if(i==N)
tt7=tt8=0;
else{
tt7=ur2[2*(N-i)-1];
tt8=dr2[2*(N-i)-1];
if(j!=N){
tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
}
}
t9=t1;
if(i%2)
t9+=t6;
else
t9+=t5;
if((j-i)%2)
t9+=t3*mod1[j*2]%MOD1;
else
t9+=t4*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt1;
if(i%2)
tt9+=tt6;
else
tt9+=tt5;
if((j-i)%2)
tt9+=tt3*mod2[j*2]%MOD2;
else
tt9+=tt4*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t2;
if(i%2)
t9+=t5;
else
t9+=t6;
if((j-i)%2)
t9+=t4*mod1[j*2]%MOD1;
else
t9+=t3*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt2;
if(i%2)
tt9+=tt5;
else
tt9+=tt6;
if((j-i)%2)
tt9+=tt4*mod2[j*2]%MOD2;
else
tt9+=tt3*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t3;
if((N-j)%2)
t9+=t8;
else
t9+=t7;
if((j-i)%2)
t9+=t1*mod1[(N-i)*2]%MOD1;
else
t9+=t2*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt3;
if((N-j)%2)
tt9+=tt8;
else
tt9+=tt7;
if((j-i)%2)
tt9+=tt1*mod2[(N-i)*2]%MOD2;
else
tt9+=tt2*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t4;
if((N-j)%2)
t9+=t7;
else
t9+=t8;
if((j-i)%2)
t9+=t2*mod1[(N-i)*2]%MOD1;
else
t9+=t1*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt4;
if((N-j)%2)
tt9+=tt7;
else
tt9+=tt8;
if((j-i)%2)
tt9+=tt2*mod2[(N-i)*2]%MOD2;
else
tt9+=tt1*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
return;
}
void insert(int x,int y){
int bucket=(x+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return;
t=t->next;
}
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
hash_count++;
return;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<HASH_SIZE;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
hash[i]=NULL;
}
return;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}
Comments :
Post a Comment