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

素颜马尾好姑娘i 2022-08-28 06:49 34阅读 0赞

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

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

![在这里插入图片描述][9f1bc58fb63e4141918b06077ba17a2e.png_x-oss-process_image]

## 1、结构体，sort比较函数重定义 ##

Memory Limit Execeed（爆内存，5分）

#include <iostream>
    #include <algorithm>
    #include <string.h>
    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<len;i++){
        
    		node[i].a = input.substr(i,k);
    		node[i].index = i+1;
    	}
    	sort(node,node+len,cmp);
    	for(int i=0;i<len;i++){
        
    		cout<<node[i].index<<" ";
    	}
    	return 0;
    }
    // baaaaccccd 3         baa aaa aaa aac acc ccc ccc ccd
    // 2 3 4 5 1 6 7 8
    // ccccdbaaaa 2         cc cc cc cd db ba aa aa aa
    // 7 8 9 6 1 2 3 4 5

## 2、pair，sort排序重定义 ##

爆内存，5分

#include <iostream>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    bool cmp(pair <string,int> x,pair <string,int> y){
        
    	return x.first < y.first;
    }
    int main()
    {
        
    	int k;
    	string input;
    	cin>>input>>k;
    	int len = input.size()-k+1;
    	pair <string,int> node[len];
    	for(int i=0;i<len;i++){
        
    		node[i] = make_pair(input.substr(i,k),i+1);
    	}
    	sort(node,node+len,cmp);
    	for(int i=0;i<len;i++){
        
    		cout<<node[i].second<<" ";
    	}
    	return 0;
    }
    // baaaaccccd 3         baa aaa aaa aac acc ccc ccc ccd
    // 2 3 4 5 1 6 7 8
    // ccccdbaaaa 2         cc cc cc cd db ba aa aa aa
    // 7 8 9 6 1 2 3 4 5

## 3、multimap，排序都省了 ##

TLE，cout7分，printf8分

#include <bits/stdc++.h>
    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<string,int> node;
    		for(int i=0; i<len; i++) {
        
    			char head = input[i];
    			if(head == (char)(a+'a'))
    				node.insert(pair<string,int>(input.substr(i,k),i+1));
    		}
    		if(!node.size()) continue;
    		multimap <string,int>::iterator it ;
    		for(it= node.begin(); it!=node.end(); ++it) {
        
    			printf("%d ",it->second);
    		}
    		node.clear();
    	}
    	return 0;
    }

## 4、节约空间的思想 ##

勉强10分  
![在这里插入图片描述][ad9140a5ade049a3afebbbddab6d719b.png]

#include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <vector>
    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<N> 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<node.size(); i++) {
        
    			int ans = node[i].index;
    			while(ans<= node[i].tail) {
        
    				printf("%d ",ans++);
    			}
    		}
    		node.clear();
    	}
    	return 0;
    }

[9f1bc58fb63e4141918b06077ba17a2e.png_x-oss-process_image]: /images/20220828/afc3445d71d2471db1deec3fda8435bb.png
[ad9140a5ade049a3afebbbddab6d719b.png]: /images/20220828/f30bf22924864c0ca63c87797ea831e5.png