问题 ：给你一个字符串s和一个字符串p，请问最少去掉s中的多少个字符，才能使得p是s的子串

本文主要是介绍问题 ：给你一个字符串s和一个字符串p，请问最少去掉s中的多少个字符，才能使得p是s的子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<string>
#include <algorithm>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::min_element;
using std::sort;

int fuc(string s, int subscript, int len, char targetchar) {
	for (int i = subscript+1; i < len; i++) {
		if (s[i] == targetchar)
			return i;
	}
	return -1;                 //-1代表没有找到目标字符
}
//快速排序
void quick_sort(int nums[], int _left, int _right) {
	int left = _left;
	int right = _right;
	int temp = 0;
	if (left < right) {                                       //如果排序的元素至少有两个则开始排序，只有一个？直接返回了
		temp = nums[left];                                    //待排序的第一个元素作为基准元素
		while (left != right) {                               //从左右两边交替扫描，直到left = right
			while (right > left && nums[right] >= temp) {
				right--;                                      //从右往左扫描，找到第一个比基准元素小的元素
			}
			nums[left] = nums[right];                         //找到这种元素nums[right]后与nums[left]交换
			while (left < right && nums[left] <= temp) {
				left++;                                       //从左往右扫描，找到第一个比基准元素大的元素
			}
			nums[right] = nums[left];                         //找到这种元素nums[left]后，与nums[right]交换
		}
		nums[right] = temp;                                   //基准元素归位
		quick_sort(nums, _left, left - 1);                    //对基准元素左边的元素进行递归排序
		quick_sort(nums, right + 1, _right);                  //对基准元素右边的进行递归排序
	}
}

int main()
{
	string s,p;
	cin >> s >> p;
	int s_len = s.length();
	int p_len = p.length();
	int a[2001][11],result[2001];
	int initials_num=0;                                              //p的首字母在s中出现的次数
	//a[j][i]代表第j个方案中p中第i个元素在s中出现的位置的下标
    //找出s中有多少个p的首元素，并记录下在s中的位置，有多少个代表有多少种查找方案        
    for (int j = 0; j < s_len; j++) {
		if (p[0] == s[j]) {
			a[initials_num][0] = j;
			initials_num++;
		}
	}
	for (int j = 0; j < initials_num; j++) {		
		result[j] = 0; 
		for (int i = 1; i < p_len; i++) {
			if (fuc(s, a[j][i-1], s_len, p[i]) != -1) {             //找到p[i],则返回下标值
				a[j][i] = fuc(s, a[j][i-1], s_len, p[i]);
				result[j] = result[j] + (a[j][i] - a[j][i-1] - 1);      //累计这个方案需要删除的字符 		
			}else {                                                   //没找到，代表方案失败。则把a[j][p_len - 1]为一个不可能的数p_len + 1，同时退出这个方案的查找
				a[j][p_len - 1] = p_len + 1;  
				result[j] = s_len + 1;                                //result[j] 也置为不可能的数s_len + 1; 
				break;
			}
		}
	}
	//下面三种任选一种都能通过测试
//用自己写的快速排序排序
	quick_sort(result, 0, initials_num-1);    //从小到大排序
	cout <<result[0]<<endl;
//调用stl算法的min_element函数求最小值	
	/*int* q = min_element(result, result + initials_num); 
    cout << *q <<endl;   */                
//调用stl算法的sort函数排序
    /*sort(result, result + initials_num);                     
    cout << result[0] << endl;    */
	return 0;
}

其实 stl算法里面的sort()函数也是快速排序。快速排序不懂的可以看我博客里面的 排序算法 这篇博客。我感觉我讲的还算容易懂。（哈哈哈哈，我膨胀了）

这篇关于问题 ：给你一个字符串s和一个字符串p，请问最少去掉s中的多少个字符，才能使得p是s的子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！