def function():
	1 最小子问题，出口，特解
	2 通释

# 给定一个字符串s和一个字符串p，请问最少去掉s中的多少个字符，才能使得p是s的子串呢？
# 解答要求时间限制：1000ms, 内存限制：100MB

# 输入
# 两行，第一行为字符串s，第二行为字符串p。(s和p只包含小写英文字母,s的长度不超过2000,p的长度不超过10,且保证有解）

# 输出
# 最少去掉的字符个数。

# 样例
# 输入样例 1
#     axb
#     ab
# 输出
#     1

# 输入样例 2
#     axabc
#     abc
# 输出
#     0

# 输入样例 3
#     axbacxbc
#     abc
# 输出
#     2

#dp[i][j]  表示 s[:i]最少需要删几个p[:j]是它的子串 O(mn) O(mn)
###

def minedit(str1,str2):
    m=len(str1)
    n=len(str2)
    # max_num=9999
    dp=[[None for i in range(n+1)]for j in range(m+1)]
    dp[0][0]=0
    for i in range(m):
        dp[i][0]=0
    for i in range(1,m+1):
        for j in range(1,n+1):
            if str1[i-1]==str2[j-1]:
                dp[i][j]=dp[i-1][j-1]
            else:
                ##
                if dp[i-1][j]!=None:
                    dp[i][j]=dp[i-1][j]+1
    result=None
    for i in range(n,m+1):
        if result==None:
            result=dp[i][n]
        else:
            result=min(result,dp[i][n])
    return result

        
print(minedit("axbacxbc","abc"))

1：首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。
2：从后向前扫描，找小于等于pivot的数，如果找到，R[i]与R[j]交换，i++。
3：从前往后扫描，找大于pivot的数，如果找到，R[i]与R[j]交换，j--。 
4: 重复2~3，直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后，以mid为界，将序列分为两部分，左序列都比pivot小，有序列都比pivot大，然后再分别对这两个子序列进行快速排序。