Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处
Author: goal00001111
Date: 29-12-08 15:50
Description:
背景 Background
第二节是英语课，今天作句型转换，ZLJ老师走了进来……
描述 Description
将陈述句转换为感叹句是英语的经典题型。因此，ZLJ老师让我们练习一下，大头的英语很差，你能帮帮他吗？
输入：第一行，一个字符串，What或How，表示感叹句由什么来引导，第二行，一个字符串，表示原句(0＜长度≤2^8)。
输出:一行，表示改后的句子(感叹句)。
样例输入 Sample Input
What
It is a lovely dog!
样例输出 Sample Output
What a lovely dog it is!
题目分析：
这道题挂”英语课句型转换“之名，行”旋转向量”之意。
而且出题者根本就没有考虑到英语语法的实际，原句有以'.'结尾的，有不符合语法的，有主语是数字的。
更变态的是感叹句的谓语只有is这个单词，主语却是任意的。
所以我们只需找到子串" is "，将其及其前面的主语（如果有的话）旋转到句末就行了。
如果子串" is "前面的主语不长，我们可以使用一个辅助字符串来存储它，然后使用一些简单的删除插入操作就能实现旋转了。
但是当主语很长时，使用辅助数组空间复杂度太大，甚至可能空间不够（当然此题足够），我们就要使用更高级的旋转算法。
此外要注意句子首字母移到句末后要改为小写。
说明：
算法思想：删除和插入。
数据结构：字符串。
时间复杂度：O(N);
空间复杂度：方法一为O(left)，left表示主语长度，方法二为O(1);
程序语言：分别用c++和pascal实现方法一，用c++实现方法二。
附注：关于向量旋转算法的详细内容请参考拙作《向量旋转算法集锦 》：
http://blog.csdn.net/goal00001111/archive/2008/12/29/3635929.aspx
方法一
c++代码：
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str1, str2;
getline(cin, str1, '/n');
getline(cin, str2, '/n');
str2[str2.size()-1] = ' '; //将句尾标号'!'改为空格' '
string temp(" is "); //只需寻找is这个单词就好了
int r = str2.find(temp) + 3;
temp = str2.substr(0, r);
if (temp[0] >= 'A' && temp[0] <= 'Z') //首字母小写
temp[0] += 'a' - 'A';
str2 = str2.substr(r, str2.size()-r); //在str2中删除temp
str1 += str2 + temp + '!'; //全部接到str1后面
cout << str1 << endl;
system("pause");
return 0;
}
PASCAL代码：
PROGRAM P1368(INPUT, OUTPUT);
CONST
capital = ['A'..'Z']; {大写字母}
VAR
str1, str2, temp : ansistring;
r : integer;
BEGIN
readln(str1);
readln(str2);
str2[length(str2)] := ' '; {将句尾标号'!'改为空格' '}
r := pos(' is ', str2) + 2; {只需寻找is这个单词就好了}
temp := copy(str2, 1, r);
if temp[1] in capital then {首字母小写}
temp[1] := chr(ord(temp[1])+32);
delete(str2, 1, r);
str1 := str1 + str2 + temp + '!';
writeln(str1);
END.
方法二
c++代码：
#include<iostream>
#include<string>
using namespace std;
void Swap(string & a, int left_1, int left_2, int len);
void GcdRotate(string & a, int n, int r);
char ToLow(char ch); //转换成小写字母
int main()
{
string str1, str2;
getline(cin, str1, '/n');
getline(cin, str2, '/n');
str2[0] = ToLow(str2[0]); //首字母小写
str2[str2.size()-1] = ' '; //将句尾标号'!'改为空格' '
int r = str2.find(" is ") + 3; //只需寻找is这个单词就好了
GcdRotate(str2, str2.size(), r);
str1 += str2;
str1 += '!';
cout << str1 << endl;
system("pause");
return 0;
}
char ToLow(char ch) //转换成小写字母
{
if (ch >= 'A' && ch <= 'Z')
ch = ch - 'A' + 'a';
return ch;
}
//交换两个长度均为len的向量块a[left_1..left_1+len) 和 a[left_2..left_2+len)
void Swap(string & a, int left_1, int left_2, int len)
{
char t;
while (len > 0)
{
t = a[left_1];
a[left_1] = a[left_2];
a[left_2] = t;
left_1++;
left_2++;
len--;
}
}
//将具有n个元素的向量a向左旋转r个位置
void GcdRotate(string & a, int n, int r)
{
if (r == 0 || r == n) //特殊情况不用旋转
return;
int lLen, rLen, pos;
lLen = pos = r;
rLen = n - r;
while (lLen != rLen)
{
if (lLen > rLen) //左半段大于右半段，移动右半段
{
Swap(a, pos-lLen, pos, rLen);
lLen -= rLen; //减少移动范围
}
else
{
Swap(a, pos-lLen, pos+rLen-lLen, lLen);
rLen -= lLen;
}
}
Swap(a, pos-lLen, pos, lLen); //最后交换中间段
}