467.环绕字符串，每日一题

题目：

把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：

"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." . 
现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 

题目意思:

存在一个收尾相连的26个字母的循环字符串s，给定一个字符串p，需要求p中连续的最长串的子串长度（相当于s而言，连续到的，因为s中z和a是连在一起的，所以zab是连续三个，abcb是连续最长3->abc）

思路：

可以用动态规划dp[i]来记录i之前用多少个连续的字母，dp[i] 记录了当前位置有多少个连续字母，一个连续字母的子串数量正好等于每个连续字母dp[i]之和，同时dp[]在创建的时候，加入哈希思路，可以去重；

代码：

/*
*findSubstringInWraproundString:把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 
char * p:给定的目标字符串
返回值：s 中 唯一 的 p 的 非空子串 的数量
*/
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int findSubstringInWraproundString(char * p){
    int dp[26];
    memset(dp,0,sizeof(dp));
    int p_len=strlen(p);
    int i;
    int k = 0;
    int sum = 0;
    for(i=0;i<p_len;i++)
    {
        if(i && (p[i]-p[i-1]+26)%26 == 1)
        {
            k++;
        }
        else
        {
            k=1;
        }
        dp[p[i] - 'a'] = MAX(dp[p[i] - 'a'], k);
    }
    for(i=0;i<26;i++)
    {
        sum += dp[i]; 
    }
    return sum;
}