首页 > ACM题库 > 九度OJ > 九度-1099-后缀子串排序[解题代码]
2013
12-12

九度-1099-后缀子串排序[解题代码]

题目来源:2010年上海交通大学计算机研究生机试真题

题目描述:

对于一个字符串,将其后缀子串进行排序,例如grain
其子串有:
grain
rain
ain
in
n

然后对各子串按字典顺序排序,即:
ain,grain,in,n,rain

输入:

每个案例为一行字符串。

输出:

将子串排序输出

样例输入:
grain
样例输出:
ain
grain
in
n
rain

cpp 代码如下:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
	string str;
	string arr[100];
	while(cin >> str){
		int len = str.length();
		for(int i=0; i<len; i++)
			arr[i] = str.substr(len-i-1,len);
		sort(arr,arr+len);
		for(int i=0; i<len; i++)
			cout << arr[i] << endl;
	}
	return 0;
}
/**************************************************************
	Problem: 1099
	User: coder
	Language: C++
	Result: Accepted
	Time:10 ms
	Memory:1524 kb
****************************************************************/


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false