学步园

字符串的故事

Time Limit:1000MS  Memory Limit:65536K
Total Submit:272 Accepted:48

Description

从前，有一串很长很长的字符串，它由n个小写字母组成。有一天它在照镜子的时候，觉得自己太肥了，于是它想减肥。减肥的时候，可以不断地去掉第一个或者最后一个字符。它希望自己减肥之后，对于小写字母a、b、c，自己身上都至少保留有一个。它想知道自己减肥后的最小长度，你能帮帮它吗？

Input

第一行有一个数字t（t ≤ 20），表示共t组数据。
接下来t行，每行有一串由小写字母组成的字符串，字符串的长度n < 100000。保证字符串中包含有小写字母a、b、c

Output

总共t行，每行输出一个数字，表示该组数据求得的最小长度。

Sample Input

2
ccbaa
abbbbbbbbbc

Sample Output

3
11

Hint

对于sample第一组数据，可以删去头尾两个字符，剩下的cba是符合要求且长度最小的。

Source

yzq

解法三：通用解法，可以将字符扩展到26个字符，即是为学论坛每日一题系列－－最短包含子串的解

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<memory.h>

const int N = 100000 ;

int main(void)
{
	int i,j,n,nBeg,nEnd,nLen,nMinLen,nSeqLen ;
	int b[N] ;
	char szStr[N] ;
	char szQueue[N] ;
	int t ;

	freopen("in.txt","r",stdin) ;
	scanf("%d",&t) ;
	while (t-- >  0)
	{
		scanf("%s",szStr) ;	
		memset(b,-1,sizeof(b)) ;
		memset(szQueue,0,sizeof(szQueue)) ;
		nBeg = nEnd = -1 ;
		nLen = strlen(szStr) ;
		n = 0 ;
		nMinLen = -1 ;

		for(i = 0 ; i < nLen ; ++i)
		{
			if(szStr[i] >= 'a' && szStr[i] <= 'c')
			{
				if(-1 == nBeg)
				{
				//	nBeg = 0 ;
					n += 1 ;
					nEnd++ ;
					nBeg = nEnd ;
					szQueue[nEnd] = szStr[i] ;
					b[szStr[i]-'a'] = nBeg  ;
				}
				else if(n >= 3 && szStr[i] == szQueue[nBeg])
				{
					nEnd++ ;
					szQueue[nEnd] = szStr[i] ;
					szQueue[b[szStr[i]-'a']] = '\0' ;
					b[szStr[i]-'a'] = nEnd ; 

					for(j = nBeg + 1 ; j < nEnd ; ++j)
					{
						if(szQueue[j] != '\0')
						{
							nBeg = j ;
							break ;
						}
					}

					nSeqLen = nEnd + 1 - nBeg ;
					if(nSeqLen < nMinLen)
					{
						nMinLen = nSeqLen ;
					}
				}
				else if(szStr[i] == szQueue[nBeg] && n < 3)
				{
					nEnd++ ;
					szQueue[nEnd] = szStr[i] ;
					szQueue[b[szStr[i]-'a']] = '\0' ;
					b[szStr[i]-'a'] = nEnd ; 

					for(j = nBeg + 1 ; j <= nEnd ; ++j)
					{
						if(szQueue[j] != '\0')
						{
							nBeg = j ;
							break ;
						}
					}
				}
				else if(b[szStr[i]-'a'] != -1)
				{
					nEnd++ ;
					szQueue[nEnd] = szStr[i] ;
					szQueue[b[szStr[i]-'a']] = '\0' ;
					b[szStr[i]-'a'] = nEnd ; 
				}
				else 
				{
					nEnd++ ;
					szQueue[nEnd] = szStr[i] ; 
					n += 1 ;
					b[szStr[i]-'a'] = nEnd ;

					if(n >= 3)
					{
						nMinLen = nEnd + 1 - nBeg ;
					}
				}
			} 
			else //排除其它字符
			{
				nEnd++ ;
				szQueue[nEnd] = '\0' ;
			}
		} 
		printf("%d\n",nMinLen) ;
	}
	return 0 ;
}

/*	---------------------------------------------------------------------------------
	嗯，这一道题之前想了很久也没有找到可行的解决方案，对，不是最优方案，而是可行方案。
	不知道怎么的，当时看到这一道题的时候，真的怎样想也没有想到解决方案。第一次做这一
	道题目的时候是一年前，那师兄家兄师兄推荐我去学算法~~~结果当时还审错题，以为只有
	abc三种，结果提交了很多次也WA，纠结了很久也没有做出来。后来也不了了之。
	一年后的最近，看看这一题，没有审错题，但是发现自己更加没有想法了。因为这道题貌似
	有很多种不确定因素。。不过，不记得那一天坐地铁，自己突然想都了突破口，但是还是没有
	找到可行方法。然后今天又是在地铁上想到了可行方案，那就是在这个突破口上面调整一下，
	结果就AC了~~~

	好，记记自己的大概思路：
	1、主要思路其实就是穷举字符串可能出现abc的各种组合，从而写出对应代码(所以，我的代码
		比较长，而且可读性不高。)

    初始情况：已经找到a、b、c中的第一个字符
    条件：在找到a、b、c三种字符中的其中一个的时候。

	情况1：再一次找到第一个发现的字符，此时abc中，只有一个字符被发现
	做法：更新pFirstFind指向的位置。

    情况2：再一次找到第一个发现的字符，此时abc中，已经有两个字符被发现
	做法：pFirstFind指向原来pSecondFind的位置,pSecondFind指向当前位置
		  分别对应更新chFirst，chSecond的值

    情况3：在已经发现一个字符的情况下，找到第二个字符
	做法：pSecondFind，chSecond处理之

    情况4：在已经发现两个字符的情况下，再一次找到第二个字符。
	做法：更新pSecondFind  (因为最短的字符串中间，只可能有一种发现字符)

    情况5：找到第三个字符
	做法：计算减肥后的长度，并与最小值比较，更新最小值

    嗯嗯，大概思路就是这样，先记下来，待有空的时候再优化

    AC，15MS。。代码很长，1.79K，家兄师兄的0MS，0.64K~~肿么会差这么多~~

	---------------------------------------------------------------------------------	*/

#include<stdio.h>
#include<string.h>

char	szInput[100005] ;

int main(void)
{
	int		i = 0 ;
	int		j = 0 ;
	int		n = 0 ;
	int		t = 0 ;
	int		nResult = 0 ;
	int		nFindTotal = 0 ;
	char	*pFirstFind , *pSecondFind , *pThridFind ;
	char	chFirst , chSecond , chThrid ;
	char	*pCurPos ;

	scanf("%d",&t) ;

	while(t-- > 0 ) 
	{
		scanf("%s",szInput) ;
		
		n = strlen(szInput) ;

		nFindTotal = 0 ;
		pFirstFind = pSecondFind = pThridFind = NULL ;
		chFirst = chSecond = chThrid = '\0' ;
		pCurPos = NULL ;
		nResult = 0 ;

		for(i = 0 ; i < n ; i++)
		{
			if('a' == szInput[i] || 'b' == szInput[i] || 'c' == szInput[i])
			{
				pFirstFind = szInput + i ;
				chFirst = szInput[i] ;
				break ;
			}
		}

		nFindTotal++ ;
		j = i + 1 ;

		for(i = j ; i < n ; i++)
		{
			pCurPos = &szInput[i] ;

			if('a' == szInput[i] || 'b' == szInput[i] || 'c' == szInput[i])
			{
				if(chFirst == szInput[i])
				{
					if(1 == nFindTotal)
					{
						pFirstFind = pCurPos ;
					}
					else if(2 == nFindTotal)		//之前错是这里忘记更新字符1和字符2的值了
					{
						pFirstFind = pSecondFind ;
						pSecondFind = pCurPos ;
						chFirst = chSecond ;
						chSecond = szInput[i] ;
					}
				}
				else if(1 == nFindTotal)
				{
					pSecondFind = pCurPos ;
					chSecond = szInput[i] ;
					nFindTotal++ ;
				}
				else if(2 == nFindTotal && chSecond == szInput[i])
				{
					pSecondFind = pCurPos ;
				}
				else if(nFindTotal < 3)
				{
					pThridFind = pCurPos ;
					chThrid = szInput[i] ;
					if(0 == nResult || pThridFind - pFirstFind + 1 <= nResult)
					{
						nResult = pThridFind - pFirstFind + 1 ;
					}
					pFirstFind = pSecondFind ;
					chFirst = chSecond ;
					pSecondFind = pThridFind ;
					chSecond = chThrid ;
				}
			}
		}
		printf("%d\n",nResult ) ;
	}	
	return 0 ;
}

/*	---------------------------------------------------------------------
	解法二：边输入，边处理

	问题：时间依然是15MS，原因是核心代码没有变，依然是穷举法。可能是比较
		  次数较多，所以依然很慢

	---------------------------------------------------------------------	*/

#include<stdio.h>
#include<string.h>

int main(void)
{
	int		t = 0 ;
	int		nResult = 0 ;
	int		nFindTotal = 0 ;
	int 	nFirstFind = 0 ;
	int		nSecondFind =  0 ;
	int		nThridFind = 0 ;
	char	chFirst , chSecond , chThrid ;
	int		nCurPos ;
	char	chCur= '\0' ;

	scanf("%d",&t) ;

	while(getchar() != '\n')
	{
		continue ;
	}

	while(t-- > 0 ) 
	{
		nFindTotal = 0 ;
		nFirstFind= nSecondFind = nThridFind = 0 ;
		chFirst = chSecond = chThrid = '\0' ;
		nCurPos = 0 ;
		nResult = 0 ;

		while((chCur = getchar()) != '\n' && chCur != EOF )
		{		
			if(('a' == chCur || 'b' == chCur || 'c' == chCur) && 0 == nFindTotal)
			{
				nFirstFind = nCurPos ;
				chFirst = chCur ;
				nFindTotal++ ;
				
				nCurPos++ ;
				continue ;
			}
			if('a' == chCur || 'b' == chCur || 'c' == chCur)
			{
				if(chFirst == chCur)
				{
					if(1 == nFindTotal)
					{
						nFirstFind = nCurPos ;
					}
					else if(2 == nFindTotal)		
					{
						nFirstFind = nSecondFind ;
						nSecondFind = nCurPos ;
						chFirst = chSecond ;
						chSecond = chCur ;
					}
				}
				else if(1 == nFindTotal)
				{
					nSecondFind = nCurPos ;
					chSecond = chCur ;
					nFindTotal++ ;
				}
				else if(2 == nFindTotal && chSecond == chCur)
				{
					nSecondFind = nCurPos ;
				}
				else if(nFindTotal < 3)
				{
					nThridFind = nCurPos ;
					chThrid = chCur ;
					if(0 == nResult || nThridFind - nFirstFind + 1 <= nResult)
					{
						nResult = nThridFind - nFirstFind + 1 ;
					}
					nFirstFind = nSecondFind ;
					chFirst = chSecond ;
					nSecondFind = nThridFind ;
					chSecond = chThrid ;
				}
			}
			nCurPos++ ;
		}
		printf("%d\n",nResult ) ;		
	}
	return 0 ; 
}