题目

较优算法

第一种

思路

遍历单词str1，与str2比较，每找到一个不同的跳过str2的一个字母，找到两个以上不同的字母直接结束；否则继续判断有几个连续相同字母，count计数

代码

#include<string.h>

#define max 1000000
char str1[max+3],str2[max+3];
int count_word[max+3];

int main()
{
    
    int count=1;
    char word;
    int sign;
    fgets(str1, sizeof(str1), stdin);
    fgets(str2, sizeof(str2), stdin);
    int flag = 1;
    int len = strlen(str1);
    for(int i=0,j=0;i<len;i++,j++)//一个一个遍历，找不同字母
    {
        
        if(str1[i]!=str2[j])/////henan  a
        {                   /////hennan n
            j++;
            word=str2[j-1];
            sign = j-1;
        }
        if(j-i>1)
        {
            flag=0;
            break;
        }
    }
    if(flag)
    {
        char *p=&str2[sign];
        while(p-1>=str2&&word==*(p-1))
        {
            count++;
            p--;
        }
        printf("%d\n",count);
        int j=0;
        while(count-j)
        {
            printf("%d %c\n",sign-(count-j)+1,word);
            j++;
        }
            
    }
    else
    {
        printf("0");
    }

    return 0;
   
}

第二种

思路

与第一种思路唯一的变化是当遇到不一样字母时将str2该字母以后前移，再与str1比较，不相同直接结束，相同继续第一种的步骤

代码

#include<string.h>

#define max 1000000

typedef struct POS
{
    int p;
    char zimu;
}pos;
pos put[max-100];
char str1[max-100],str2[max-100];
int count_word[max-100];

int main()
{
    
    int count=1;
    char word;
    fgets(str1, sizeof(str1), stdin);
    fgets(str2, sizeof(str2), stdin);
    int flag = 1;
    int len = strlen(str1);
    for(int i=0;i<len;i++)//一个一个遍历，找不同字母
    {
        
        char word;

        if(str1[i]!=str2[i])/////henan  a
        {                   /////hennan n
            word=str2[i];
            for(int j=i+1;j<=len;j++)//平移一位
            {
                str2[j-1]=str2[j];
            }
            str2[strlen(str2)-1]='\0';
            if(strcmp(str2,str1)!=0)
            {
                flag=0;
                break;
            }
            else
            {
                char *p=&str2[i];
                while(p-1>=str2&&word==*(p-1))
                {
                    count++;
                    p--;
                }
                
                int j=0;
                while(count-j)
                {
                    put[j].p=i-(count-j)+1;
                    put[j].zimu=word;
                    
                    j++;
                }
            }
            break;
        }
        
        
    }
    if(flag==0)
    {
        printf("0\n");
    }
    else
    {
        printf("%d\n",count);
        for(int i=0;i<count;i++)
        {
            printf("%d %c\n",put[i].p,put[i].zimu);
        }
    }
}

启示

写这题的启示：

1. 写代码前先思考优化代码，不要直接暴力算法

2. strlen不要放在循环条件里，（包括判断条件）