【算法】kstring(字符串子序列重排序)

给定一个长度为n
的只包含小写字母的字符串S，请对所有长度为k的子串进行排序，输出排好序的下标序列。

按照字典序从小到大排序，如果子串一样，那么左端点下标小的更小(排在前面)。

Memory Limit Execeed（爆内存，5分）

#include 
#include 
#include 
using namespace std;
struct Node{
	string a;
	int index;
};
bool cmp(Node x,Node y){
	return x.a < y.a;
}
int main()
{
	int k;
	string input;
	cin>>input>>k;
	int len = input.size()-k+1;
	struct Node node[len];
	for(int i=0;i 
2、pair，sort排序重定义 
爆内存，5分
 
#include 
#include 
#include 
using namespace std;
bool cmp(pair  x,pair  y){
	return x.first < y.first;
}
int main()
{
	int k;
	string input;
	cin>>input>>k;
	int len = input.size()-k+1;
	pair  node[len];
	for(int i=0;i 
3、multimap，排序都省了 
TLE，cout7分，printf8分
 
#include 
using namespace std;
int main()
{
	int k;
	string input;
	cin>>input>>k;
	int len = input.size()-k+1;
	for(int a=0; a<26; a++) {
		multimap node;
		for(int i=0; i(input.substr(i,k),i+1));
		}
		if(!node.size()) continue;
		multimap ::iterator it ;
		for(it= node.begin(); it!=node.end(); ++it) {
			printf("%d ",it->second);
		}
		node.clear();
	}
	return 0;
}
 
4、节约空间的思想 
勉强10分
 
 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct Node {
	string a;
	int index,tail;
} N;
bool cmp(N x,N y)
{
	return x.a < y.a;
}
int main()
{
	int k;
	string input,pre="";
	cin>>input>>k;
	int len = input.size()-k+1;
	vector node;
	for(int a=0; a<26; a++) {
		for(int i=1; i<=len; i++) {
			char head = input[i-1];
			if(head == (char)(a+'a')) {
				string subs = input.substr(i-1,k);
				if(pre != subs) {
					pre = subs;
					N tmp;
					tmp.a  =  subs;
					tmp.index = i;
					tmp.tail = i;
					node.push_back(tmp);
				} else {
					node[node.size()-1].tail = i;
				}
			}

		}
		if(!node.size()) continue;
		sort(node.begin(),node.end(),cmp);
		for(int i=0; i