求一个串中最长的串，使得该串中出现的不同的字母数最大为m，求该子串的最大长度。
搞两个指针Pi,Pj，初始化Pi=0,Pj=1，然后每次Pj要移动的时候，看Pi到Pj之间的不同的字母数是否为m，如果为m的话，就移动Pi指针，直到不为m，然后把，Pj向右移动一下，这样的串是肯定存在的，即任意一个长度为1的子串都是符合条件的，所以Pi<Pj，所以复杂度为O(n)，然后统计Pi，Pj之间的不同的字母数，可以用数组来统计，做到复杂度为O(1)。总的复杂度就为O(n)，用队列来维护这个过程。
代码 #include < iostream > #include < math.h > #include < deque > #include < string > #include < vector > #include < string .h > #include < stdio.h > #include < algorithm > using namespace std; const int MAX = 100005 ; char ch[MAX]; int len; int go( int b){ if (len == 1 && ch[ 0 ] <= ' 9 ' ) return ch[ 0 ] - ' 0 ' ; int res = 0 ; for ( int i = 0 ; ch[i] != ' \0 ' ; i ++ ) { res = res * 10 + ch[i] - ' 0 ' ; res %= ( 10 - b); } res = (res - 10 ) % ( 10 - b); while (res < 0 ) res += ( 10 - b); return res + b;} int main(){ while (gets(ch)) { len = strlen(ch); for ( int i = 1 ; i <= 9 ; i ++ ) { if (i == 1 ) printf( " %d " , go(i)); else printf( " %d " , go(i)); } printf( " \n " ); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/12/31/1923325.html
相关资源：数据结构—成绩单生成器