辗转相除法——字符串处理
GCD:辗转相除法，求两个正整数的最大公约数。
gcd(m,n) = gcd(n,m mod n) ［a>b且 a mod b不等于0］
步骤：
1. 求余数r = m%n
2. 若r＝0，则算法结束，此时的n就为m和n的最大公约数。
3. 否则，令m = n, n = r，返回第一步。
目标：rotate(s,m)
将字符串s的前m位左旋至末尾。
例：s = abcdefghijk
rotate(s,3) ＝ defghijkabc
思路：
1. 假设字符串s需要调整位置，设置指针p1指向s起点，p2指向起点+m的位置，这里p1->a, p2->d。
2. 交换p1和p2指向的元素，同时让p1++, p2++。 这样的动作持续 k = (n-m) - (n%m) 次，其中n为s的长度。
为什么要这么多次呢？上例中，n=11, m =3，则k等于 (11-3) - (11%3) = 6次。经过6次第二步的操作以后s变成了defghi abc jk。式子中11%3的意思是不够m位的部分，11-3的意思是以p2为坐标，到字符串s尾巴距离多少。进入步骤3.
3. 此时s＝defghi abc jk，这时我们只需要将jk移动到abc前面即可，而前面的部分defghi不用管。所以这里只关心abcjk这一部分，设为s。此时s的长度为5，移动的目标是jk，长度m=2。p1指向尾巴，p2指向尾巴-m的位置。交换p1和p2指向的元素，同时让p1--, p2--。（例如，第一次就是k与c交换位置，然后p2指向b，p1指向j）。这样的动作持续k=(n-m) - (n%m)次。 （其实这步的操作就完全和步骤2相反）。执行完步骤3后，返回步骤2.
4. 当s的头尾指针指向一个元素，或者m＝0的时候，结束递归。
java代码如下
private static void rotate(String array, int n, int m, int head, int tail, boolean flag){
int j = 0;
if (head == tail || m <= 0) return;
//right move
if (flag == true){
int p1 = head;
int p2 = head + m;
int k = (n-m) - (n % m);//移动的次数
for(int i = 0; i< k; i++, p1++, p2++){
array = swap(array,p1,p2);
}
rotate(array, n-k, n%m, p1, tail, false);//enter the left move
}
else{
int p1 = tail;
int p2 = tail - m;
int k = (n-m) - (n%m);
for(int i = 0; i
array = swap(array,p1,p2);
}
rotate(array,n-k, n%m, head, p1, true);
}
}
方法2
对于一个字符串s = ab. a和b是s的子字符串。假设a长度为m，那么目标就是经过了rotate(s,m)操作后，s变成ba。
思路
对于s=ab，有ba = (a'b')'
其中a'等于a的反转，例如a ＝ abc，那么a' = cba
假设s=abcdefg，那么a=abc, b= defg，则rotate(s,m) = (a'b')' = cbagfed=defgabc。
代码
字符串反转部分
public static String reverse(String s){
if(s.length()<=0 || s == null) return s;
return reverse(s.substring(1)) + s.charAt(0);
}
这里利用了递归的思想：如果我要反转s，我可以先把s的第一个元素放到最后，然后单独对剩下的s-1个元素进行反转操作。（汉诺塔问题的解决方法）
rotate(s,m)
public static String rotate(String s, int m){
String sa = s.substring(0, m);
String sb = s.substring(m);
return reverse(reverse(sa) + reverse(sb) );
}
问题描述： 两个字符串S1和S2，假设S1长度大于等于S2长度，判断S2是否为S1的一个子集。 例如：S1=ABCDEFGHI, S2=ACEFG，由于S2中的每个元素都出现在S1中，说明S1包含S2. 若S2=ACEFGK, 由于K不在S1中，因此S1不包含S2。
设S1长度为m，S2长度为n 方法1: Brute-Force 两个for loop，复杂度为O(m*n)
public static boolean compare(String[] s1, String[] s2){
//s1:longString[]; s2:shortString[]
int i,j;
for(i = 0; i
{
for(j = 0; j
{
if(s2[i].compareTo(s1[j])==0)
break;
}
//s2中的一个字符遍历了s1还是没找到，即没有执行break使得j达到了s1.length
if (j==s1.length) return false;
}
return true;
}
方法2: 对s1和s2先排序，例如quicksort，则复杂度为O(mlgm)+O(nlgn)+O(m+n) 首先是quicksort部分
public static int partition(String[] array,int lo, int hi){
String pivot = array[lo];
int i = lo;
int j = lo + 1;
while(j<=hi){
if(array[j].compareTo(pivot)<0){
i++;
exch(array,i,j);
}
j++;
}
exch(array,lo,i);
return i;
}
private static void exch(String[] array, int i, int j){
String temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void quickSort(String[] array){
quickSort(array, 0, array.length-1);
}
private static void quickSort(String array[], int lo, int hi){
if(hi<=lo) return;
int i = partition(array,lo,hi);
quickSort(array,lo,i-1);
quickSort(array,i+1,hi);
}
在执行下面的代码前，要对s1和s2用quicksort重新排好序。
public static boolean compare(String[] s1, String[] s2){
int p1 = 0;
int p2 = 0;
while(p1
while(s1[p1].compareTo(s2[p2])<0 && p1
if(s1[p1].compareTo(s2[p2])!=0) break;
p2++;
}
if(p2==s2.length) return true;
else return false;
}
方法3 利用counting sort，可以将复杂度降低至线性。即O(m) + O(n) + O(m+n) = O(m+n) 计数排序的代码如下：
public static String[] countingSort(String[] array){
int[] c = new int[26];
for (int i = 0; i <26; i++)
{
c[i] = 0;
}
String[] b = new String[array.length];
//初始化辅助数组
for (int i = 0; i
{
int ind = ((int)array[i].toCharArray()[0] - (int)("a".toCharArray())[0]);
c[ind] = c[ind] + 1;
}
for (int i = 1; i<26; i++)
{
c[i] = c[i] + c[i-1];
}
for(int i = array.length-1; i>=0; i--)
{
int ind = ((int)array[i].toCharArray()[0] - (int)("a".toCharArray())[0]);
b[c[ind]-1] = array[i];
c[ind] = c[ind] - 1;
}
return b;
}
之后如同方法2，调用compare即可
方法4 用hashtable，将短的字符串的每个元素存储在一张hash table中，O(n)。然后对长字符串进行遍历，看hash(s1[i])映射到的slot是否已经有元素了。如果全部都有，则说明s1包含s2，如果有一个slot是空的，则说明s1不包含s2. 复杂度O(m)。所以总的复杂度是线性的。O(m+n)
public static boolean compare(String[] s1, String[] s2){
int[] hash = new int[26];//初始化hash
for(int i = 0; i
{
hash[i] = 0;
}
int num = 0;
for(int i = 0; i
{
int ind = ((int)s2[i].toCharArray()[0] - (int)("a".toCharArray())[0]);
if (hash[ind] == 0)
{
hash[ind] = 1;
num++;
}
}
for(int i = 0; i
{
int ind = ((int)s1[i].toCharArray()[0] - (int)("a".toCharArray())[0]);
if(hash[ind] == 1)
{
hash[ind] = 0;
num--;//一个字符匹配到
if(num==0) break;
}
}
if(num==0) return true;
else return false;
}
