プログラミングの方法-文字列の回転

文字列の回転
本文のブログはjuly大神の著作「プログラミングの法-面接とアルゴリズムの心得」の文字列の1章に基づくメモです.julyは、大学1年生の时からずっと彼のブログを読んで、最も基础的なアルゴリズムから、それから闻くと高い机械の学习のアルゴリズムまで、googleの1つのアルゴリズムが分からない时julyのブログを拝読して、1年来ずっとjuly大神のブログの影响を受けていると言えます.本文はこの本の第1章である文字列の回転である.タイトルの説明:文字列の前のいくつかの文字を文字列の末尾に移動する必要がある文字列を指定します.たとえば、文字列「abcdef」の最初の3文字「a」、「b」、「c」を文字列の末尾に移動すると、元の文字列は「defabc」になります.この機能を実装する関数を書いてください.解法1:この問題を初めて見ると、移動する文字を文字列の末尾に1つずつ移動する方法が最初に考えられるかもしれません.コードは次のとおりです.

void leftShiftOne(char *s,int n)
{
	char t = s[0];
	int i;
	for(i=1;i<n;i++)
		s[i-1]=s[i];
	s[n-1]=t;
}

は次に、この関数をm回呼び出し、文字列の先頭のm文字を文字列の末尾に移動させる.

void LeftRotateString(char *s,int n,int m)
{
	while(m--)
	{
		leftShiftOne(s,n);
	}
}

これでタスクを完了できますが、時間の複雑さがO(mn)であることがわかりました.では、この複雑さを低減する方法はありますか?
解法2:1つの文字列を2つの部分に分割し、2つの部分の文字列をそれぞれ反転させ、最後に文字列全体を全体的に反転させることで目的を達成することができます.くだらないことは言わないで、コードをつけます:

#include"stdio.h"
void ReverseString(char *s,int from,int to)
{
	while(from<to)
	{
		char t =s[from];
		s[from++]=s[to];
		s[to--]=t;
	}
}
void LeftRotateString(char *s,int n,int m)
{
	ReverseString(s,0,m-1);
	ReverseString(s,m,n-1);
	ReverseString(s,0,n-1);
}
int main()
{
	char s[]="abcdef";
	LeftRotateString(s,6,3);
	printf("%s",s);
	system("pause"); 
	return 0;
}

時間複雑度はO(n)であった.
練習:英語の文を入力して、文の中の単語の順序を反転して、単語の内の文字の順序が変わらないことを要求して、文の中の単語はスペースで隔てられています."I am a student."「student.a am I」に反転します.
問題を解く構想:3部の反転法、まず全体を反転して、それから1つの単語を判断して反転して、目標を実現することができます.コードは次のとおりです.

void ReverseString(char *s,int from,int to)
{
	while(from<to)
	{
		char t =s[from];
		s[from++]=s[to];
		s[to--]=t;
	}
}

void ReverseWords(char *s,int n)
{
	ReverseString(s,0,n-1);
	int i=0,j=0;
	for(i=0,j=0;j<n;j++)
	{
		if(j==n || s[j+1]==' ')
		{
			ReverseString(s,i,j);
			i=j+2;
		}
	}
}

mainメソッドでReverseWordsを呼び出す
方法でいいです.