// Two-star problem // Problem 10298 Power Strings /* This program is written by Prof. Chua-Huang Huang Department of Information Engineering and Computer Science Feng Chia University Taichung, Taiwan Disclaimer: The programming problem is downloaded from UVa Online Judge (https://uva.onlinejudge.org/). The program solution is provided for helping students to prepare Collegiate Programming Examination (CPE). The author does not guarantee the program is completely correct to pass UVa Online Judge platform or CPE examination platform. This program is not intended for a student to copy only. He/She should practice the programming problem himself/herself. Only use the program solution as a reference. The author is not responsible if the program causes any damage of your computer or personal properties. No commercial use of this program is allowed without the author's written permission. */ #include #include #include int main(void) { char s[1000001]; // The input string, not exceed 1 million characters. char letter[2]; // A string of single character for searching next substring. int length; // Length of string s. int sublength; // Length of a substring. char **subs; // A collection of substrings of s, each of length sublength. int subcount; // The number of substings in subs[]. int max_subcount; // The maximum number of substings in subs[]. int incremental = 10; int n; // Maximum power. int power; // Power of the current substring. int inx; // The character index of the current substring. int next; // The character index of the next substring in searching. int duplicate; // 0: no duplicate substring; 1: otherwise. int i; // Loop variable. while (1) { // Continue until the input string is a period. scanf("%s", s); // Input a testing string. if (strcmp(s, ".")==0) break; // If the string is a period, stop the loop. length = strlen(s); // Number of characters in string s. sublength = 1; // Start subsrtings with length 1. subcount = 0; // No substring yet. max_subcount = incremental; // Initially, "incremental" (10) substrings. // Allocate memory for comparing substrings. subs = (char **) malloc(sizeof(char *) * max_subcount); for (i=0; in) { strncpy(subs[subcount], s+inx, sublength); // Copy a substring to compare. subs[subcount++][sublength] = '\0'; // Add end-of-string. // If the memory of the substring is full, request more memory. if (subcount==max_subcount) { max_subcount += incremental; // Increase the maximum substring count. subs = (char **) realloc(subs, sizeof(char *) * max_subcount); // Ask for more entries. // Request memory for the newly created pointers. for (i=max_subcount-incremental; i