包含集合的最短子串

有一个子串和一个集合,集合中的字符不重复,求子串中最短的包含集合的子串长度,如果不存在,返回0

例:

set: abc

string: axbyczab

return: czab 4


方法:用滑动窗口加上状态位来解决

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include <limits.h>
using namespace std;

int hashs[256];
int getMin(char str[],int n, char *src)
{
    int i;
    int num=0;
    int len = INT_MAX;
    for(i=0;i<256;i++)
        hashs[i] = -1;
    for(i=0;i<n;i++)
        hashs[str[i]] = 0;
    char *p = src, *q = src;
    while(*p!=0&&num<n)
    {
        if(hashs[*p]!=-1)
        {
            if(hashs[*p]==0)
                num++;
            hashs[*p]++;
        }
        p++;
    }
    if(*p==0&&num!=n)
        return 0;
    len = p - q ;
    while(q!=p)
    {
        if(hashs[*q]==-1)
            q++;
        else
        {
            hashs[*q]--;
            if(hashs[*q]==0)
            {
                if(p-q<len)
                    len = p -q;
                hashs[*q]++;
                break;
            }
            q++;
        }
    }
    while(*p!=0)
    {
        if(hashs[*p]==-1)
            p++;
        else
        {
            hashs[*p]++;
            while(q!=p)
            {
                if(hashs[*q]==-1)
                    q++;
                else
                {
                    hashs[*q]--;
                    if(hashs[*q]==0)
                    {
                        if(p-q+1<len)
                            len = p -q+1;
                        hashs[*q]++;
                        break;
                    }
                    q++;
                }
            }
            p++;
        }
    }
    return len;
}
int main()
{
    char str[10];
    char src[100];
    int n;
    int result;
    while(cin>>str)
    {
        int len = strlen(str);
        cin>>src;
        result = getMin(str, len, src);
        cout<<result<<endl;
    }
    return 0;
}


每天早上叫醒你的不是闹钟,而是心中的梦~
原文地址:https://www.cnblogs.com/vintion/p/4116824.html