How to use C++ String in Competition

Today, we are going to talk about C++ String and how to use it in competition. Since it is my first blog about USACO or CCF(In China) competition. And also It works for Computer Science students in USA. This article will divide as two parts. Each part will explain char and String in C or C++.

Char in C

Basic info

Remember there is no String in C! String belong to C++’s library. Now you see the privilege of C++.

Declare:

1
2
3

char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};//char end with '\0' which Means NULL
//Or
char greeting[] = "Hello";

Warning: You need to be awared that when to use‘’, and when to use“”.

Here is how it is stored in computer, Warning: Count start with 0!!!

![](String In C and C++/string_representation.jpg)

Printout

1	printf("%s", greeting );//"Hello" will be print

Six functions about Char

Here is the example for strcpy and strcat and strlen, and I will explain in the Annotation

#include <stdio.h>
#include <string.h>//The name is String, but there is still no way you can declare string in c
int main (){
   char str1[12]="Hello",str2[12]="World",str3[12];
  
   /* Copy str1 to str3 */
   strcpy(str3, str1);
   printf("strcpy( str3, str1) :  %s\n", str3 );
  
   /* Link str1 and str2 */
   strcat( str1, str2);
   printf("strcat( str1, str2):   %s\n", str1 );
  
   /* The length of str1*/
   int len = strlen(str1);
   printf("strlen(str1) :  %d\n", len );
   return 0;
}

Here is the output:

1
2
3

strcpy( str3, str1) :  Hello
strcat( str1, str2):   HelloWorld
strlen(str1) :  10

Remeber to be careful about the size of the array!

And here are three other functions which would be a little compacte

strcmp

Use: Compare 2 strings if they are same or not, same return 0

Explain: The function compare their ascil number, from the first index of the string to the end, if their ascil number equal then continue, if they are not equal then return their difference.

#include <string.h>
int main(){
    char *p="aBc";
    char *q="Abc";
    char *h="aBc";
    printf("strcmp(p,q):%d\n",strcmp(p,q));
    printf("strcmp(p,h):%d\n",strcmp(p,h));
    return 0;   
}
/*
strcmp(p,q):32   (97-65)
strcmp(p,h):0
*/

FAQ Ascil chart

![](String In C and C++/Ascii.png)

Remember ‘a’=97, ‘A’=65.

strchr and strstr

They looks like brother to me. The function strchr(str1,ch) return an array point to the place where ch first appear in str1. And The function strctr(str1,str2) return an array point to the place where str2 first appear in str1.

Code

#include <stdio.h>
#include <string.h>
int main (){
   const char str[] = "http://www.github.com";
   const char ch = '.';
   char *ret;
   ret = strchr(str, ch);
   printf("After |%c| the string is - |%s|\n", ch, ret);
   char *substr = "www.";
    char *s = strstr(str, substr);
    printf("After |%s| the string is - |%s|\n",substr,s);
   return 0;
}
/*Output
After |.| the string is - |.github.com|
After |www.| the string is - |www.github.com|
*/

Reminder: Those function will keep the string we are searching!

String in C++

We can treat C++ as the son of C, so it inherits all the libaray from C. Which means that all the things above is also available for C++. But as the son of C, C++ have some new extensions that are not available in C.

String in C++ is much more easy to understand. It was as the same level as int and long long, which means we can add the strings!

#include <iostream>
#include <string>//Remember to put this libaray in!
using namespace std;
int main (){
   string str1 = "Hello";
   string str2 = "World";
   string str3;
   // copy str1 to str3
   str3 = str1;
   cout << "str3 : " << str3 << endl;
 
   // Link str1 with str2
   str3 = str1 + str2;
   cout << "str1 + str2 : " << str3 << endl;
 
   // The length of str3
   int len = str3.size();
   cout << "str3.size() :  " << len << endl;
 
   return 0;
}
/*
str3 : Hello
str1 + str2 : HelloWorld
str3.size() :  10
*/

Examples and Solutions!

~~Warning: those are not for beginners!~~

I chose the question from USACO 1.3.3 Calf Flac

Here is the question:

1
2
3

It is said that if you give an infinite number of cows an infinite number of heavy-duty laptops (with very large keys), that they will ultimately produce all the world’s great palindromes. Your job will be to detect these bovine beauties.
Ignore punctuation, whitespace, numbers, and case when testing for palindromes, but keep these extra characters around so that you can print them out as the answer; just consider the letters `A-Z’ and `a-z’.
Find the largest palindrome in a string no more than 20,000 characters long. The largest palindrome is guaranteed to be at most 2,000 characters long before whitespace and punctuation are removed.

SAMPLE INPUT (file calfflac.in)

1	Confucius say: Madam, I'm Adam.

OUTPUT FORMAT

The first line of the output should be the length of the longest palindrome found. The next line or lines should be the actual text of the palindrome (without any surrounding white space or punctuation but with all other characters) printed on a line (or more than one line if newlines are included in the palindromic text). If there are multiple palindromes of longest length, output the one that appears first.

SAMPLE OUTPUT (file calfflac.out)

1 2	11 Madam, I'm Adam

Solution

This question takes no hard thinking. Because the data is small(20,000Index) so that we try every single index of the sequence. Then it should be divided into two cases.

Parlindrome’s length is odd
Parlindrome’s length is even

And we have a varible to save the length every time we found a new palindrome. At the end we just need to print if out. Here is the code:

#include <iostream>
#include<cstring>
#include <ctype.h>//Use this to allow you to use isalpha(k[i]) and tolower(k[i])
using namespace std;
#define mx 20005
int at[mx],n=0,l=0,maxn=0,ans;
char k[mx]={0},m[mx]={0};
int palindromes(int x){
	int a1=1,a2=0;
	for(int i=1;x-i>=0&&i+x<l&&m[x-i]==m[x+i];i++)a1+=2;//Get 1 from middle, length is odd
	for(int i=0;x-i>=0&&i+x+1<l&&m[x-i]==m[x+i+1];i++)a2+=2;//Get 2 from middle, length is even
	return (a1>a2)?a1:a2;//Get the bigger one
}
int main() {
	while((k[n]=getchar())!=EOF)n++;//Special kind of put in, I will write ablog about it someday
	for(int i=0;i<n;i++){
		if(isalpha(k[i])){//Judge ifk[i]is alpha
			m[l]=tolower(k[i]);//If k[i] is bigger case, put it to lower
			at[l++]=i;//at save the place the new m[l]'s place in k[]
		}
	}
	for(int i=0;i<l;i++){
		int t=palindromes(i);
		if(t>maxn){
			maxn=t;ans=i+(t/2);//Save the longest for now
		}
	}
	k[at[ans]+1]='\0';
	cout<<maxn<<endl;
	cout<<k[at[ans-maxn+1]];
	return 0;
}

Hahhhhh?

You don’t understand some code segment????????

Sure. I will change those with the way that’s easier for you.

1
2
3

for(int i=1;x-i>=0&&i+x<l&&m[x-i]==m[x+i];i++)a1+=2;//Get 1 from middle, length is odd
for(int i=0;x-i>=0&&i+x+1<l&&m[x-i]==m[x+i+1];i++)a2+=2;//Get 2 from middle, length is even
return (a1>a2)?a1:a2;//Get the bigger one

Can be write in this way:

for(int i=1;i<=x;i++){
			if(i+x<l&&m[x-i]==m[x+i])
				a1+=2;
			else
				break;
	}
for(int i=0;i<=x;i++){
			if(i+x+1<l&&m[x-i]==m[x+i+1])
				a2+=2;
			else
				break;
	}
if(a1>a2)return a1;
else return a2;

And for those kind of code:

1
2
3

if(isalpha(k[i])){//Judge ifk[i]is alpha
		m[l]=tolower(k[i]);//If k[i] is bigger case, put it to lower
	}

If you don’t know those functions, we can actually write it ourslves.

int h=(int)k[i];
if(h>=65&&h<=90){
	m[l]=(char)(h+32);//'A'=65,'Z'=90,'a'=97,'z'=122
}

Conclusion

Question around String won’t be so hard. As long as we use the function properly. The best way for you to improve is not just to read this blog, but to exercise.