【CareerCup】 Arrays and Strings—Q1.7

전재 출처 를 밝 혀 주 십시오:http://write.blog.csdn.net/postlist/0/all/draft
   
    제목:
    Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring ( i.e., “waterbottle” is a rotation of “erbottlewat”).
    번역:
    하나의 문자열 이 다른 문자열 의 하위 문자열 인지 판단 할 수 있 는 isSubstring 함수 가 있다 고 가정 하면 주어진 문자열 s1 과 s2 에 대해 프로그램 을 작성 하고 isSubstring 을 한 번 만 호출 하면 s2 가 s1 의 회전 문자열 인지 판단 할 수 있 습 니 다.예 를 들 어 'waterbottle' 은 'erbottlewat' 의 회전 문자열 이다.
    번역:
    회전 문자열 은 문자열 의 앞 (뒤) 몇 개의 문 자 를 뒤로 옮 기 는 것 을 말 합 니 다.
    제목 에서 isSubstring 을 사용 하 라 고 요구 하고 한 번 만 사용 할 수 있 습 니 다. 이 함 수 를 사용 하려 면 두 문자열 의 길이 가 같 지 않 고 s1 과 s2 에 직접 이 함 수 를 사용 할 수 없습니다.회전 문자열 은 앞 에 있 는 것 이 뒤쪽 이나 뒤쪽 으로 만 이전 되 었 기 때문에 s1 + s1 을 다음 에 s2 가 s1 + s1 의 하위 문자열 인지 판단 할 수 있 습 니 다. 그렇다면 s2 가 s1 의 회전 문자열 임 을 증명 합 니 다.위의 "erbottlewat"+ "erbottlewat"= 'erbottlewaterbottlewat' 는 분명히 'waterbottle' 은 그 하위 꼬치 (앞의 굵 은 부분) 이다.
    구현 코드:    

bool isRotate(string s1,string s2)
{
	if(s1.length() != s2.length())
		return false;
	return isSubstring(s1+s1,s2);
}

    실현 코드 는 매우 간단 하고 isSubstring 함 수 는 KMP 알고리즘 으로 실현 할 수 있 습 니 다. 우 리 는 더 이상 테스트 하지 않 습 니 다!
    다음은 회전 문자열 을 중심 으로 문 제 를 살 펴 보 겠 습 니 다.
    첫 번 째 k 자리 이전 (0 부터 계산) 의 문 자 를 이 문자열 의 끝 부분 으로 회전 시 켜 회전 한 문자열 을 찾 습 니 다.예 를 들 어 문자열 'abcdef' 에 대해 두 번 째 위치 앞의 문 자 를 끝까지 회전 시 켜 'cdefab' 을 얻 습 니 다.공간 복잡 도 는 O (1) 이 고 시간 복잡 도 는 O (n) 이다.
    생각:
    생각 하기 쉬 운 방법 은 len + 1 길이 의 문자 배열 (마지막 으로 '\0' 을 저장 하 는 데 사용) 을 따로 만 드 는 것 입 니 다. 원래 문자열 의 k 위 이전의 문 자 를 문자 배열 뒤에 복사 하고 k 위 (k 위 포함) 뒤의 문 자 를 문자 배열 의 앞 에 복사 하 는 것 입 니 다. 이렇게 하면 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (n) 입 니 다.
    제목 에서 공간 복잡 도 는 O (1), 즉 회전 은 제자리 에서 해 야 한다. 우 리 는 이렇게 할 수 있다. 먼저 회전 해 야 할 두 부분의 문 자 를 각각 반전 시 킨 다음 에 전체 문자열 을 반전 시 키 면 원 하 는 회전 문자열 을 얻 을 수 있다.예 를 들 어 'abcdef' 는 회전 을 통 해 'cdefab' 를 얻 으 려 면 'ab' 와 'cdef' 를 각각 반전 시 키 고 'bafedc' 를 얻 은 다음 에 'bafedc' 를 반전 시 키 고 요 구 된 회전 문자열 을 'cdefab' 로 바 꿀 수 있 습 니 다.
    구현 코드:

/****************************************************************************************
题目描述：
已知一个字符串，将其第k个位之前（从0开始计）的字符旋转至该字符串的尾部，求旋转后的字符串。
比如，对于字符串“abcdef”，将其第2个位置前的字符旋转至尾部，得到“cdefab”。
Date:2014-03-19
*****************************************************************************************/

#include<stdio.h>
#include<string.h>

/*
将字符串str的start和end位置之间的字符反转
*/
void reverseString(char *str,int start,int end)
{
	while(start < end)
	{
		str[start] = str[start] + str[end];
		str[end] = str[start] - str[end];
		str[start] = str[start] - str[end];
		start++;
		end--;
	}
}

/*
进行三次反转
*/
void rotate(char *str,int k)
{
	int len = strlen(str);
	if(k <= 0 || len <= k)
		return ;
	reverseString(str,0,k-1);
	reverseString(str,k,len-1);
	reverseString(str,0,len-1);
}

int main()
{
	char str1[] = "abcdef";
	char str2[] = "abcdefghket";
	rotate(str1,1);
	rotate(str2,4);
	puts(str1);
	puts(str2);
	return 0;
}

    테스트 결과: