| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3123 人关注过本帖
标题:求教,字符串最长的前后缀匹配
只看楼主 加入收藏
huicpc0876
Rank: 2
等 级:论坛游民
帖 子:69
专家分:50
注 册:2009-7-24
结帖率:92.59%
收藏
已结贴  问题点数:20 回复次数:13 
求教,字符串最长的前后缀匹配
题目,输入两个字符串a,b,当a的前几个字符,和b的后几个字符相等的是前缀和后缀的匹配,输出最大的匹配字符串和长度。
Sample Input
clinton
homer

riemann
marjorie
 
Sample Output
0/*表示不存在匹配的时候*/
rie 3
 
我写了一个代码,但是运行不起来,也不知道怎么错了,谁能顺便帮我改改是最好了。
#include"stdio.h"
#include"string.h"
char a[50001],b[50001];
int c[50001];

int main()
{ unsigned int  i=0,j,n,t,flag,alen,blen;
  while(gets(a)!=NULL)
  {
   gets(b);
   flag=0;
   alen=strlen(a);
   blen=strlen(b);/*读入两个字符串,求长度*/
     for(j=blen-1;j>=0;j--)
      {
      if(b[j]==a[0]) c[j]=1;
       else c[j]=0;
       }/*b数组中存在一个和a[0]相等的,标志数组置为1,否则初始为零*/
      for(t=0;t<=blen-1;t++)
         {if(c[t]==1)/*当c【】为1的时候,说明b中有个字符和a【0】相等*/
            {  j=t;i=0;/*b[]从c记录的下标开始和a【1,2,3,4.。。】相比较,*/
               while( b[j]==a[i])
         
              { j++;
                i++;
                if(j>blen-1) {flag=1; break;}/*b【】数组比较完毕,找到,标志位置为1*/
                else  if(i>alen-1) {         break;}
               }
             }
          }   
   if(flag==0) printf("%d\n",flag);
   if(flag==1)
      {
         for(i=t;t<blen;t++)
         {printf("%c",b[t]);}
         
          printf(" %d\n",i+1);
       }   

  }

  return 0;

}
搜索更多相关主题的帖子: 后缀 字符 
2009-08-04 21:54
godbless
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:216
专家分:950
注 册:2009-7-24
收藏
得分:0 
下面这个循环是死循环,自己好好想想。。。

for(j=blen-1;j>=0;j--)
      {
      if(b[j]==a[0]) c[j]=1;
       else c[j]=0;
       }/*b数组中存在一个和a[0]相等的,标志数组置为1,否则初始为零*/
2009-08-04 23:25
hewenhao
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2007-1-10
收藏
得分:0 
回复 楼主 huicpc0876
另外一个比较严重的问题:
题目要求输出最长的匹配字符串,可楼主代码中遇到第一个匹配的串就退出并输出了

2009-08-04 23:56
huicpc0876
Rank: 2
等 级:论坛游民
帖 子:69
专家分:50
注 册:2009-7-24
收藏
得分:0 
回复 2楼 godbless
是不是因为我之前定义的是unsigned int ,所以j始终>=0,所以死循环了?
但是程序还有发现错误么,我将
for(j=blen-1;j>=0;j--)
      {
      if(b[j]==a[0]) c[j]=1;
       else c[j]=0;
       }/*b数组中存在一个和a[0]相等的,标志数组置为1,否则初始为零*/
改为
for(j=0;j<=blen-1;j++)
      {
      if(b[j]==a[0]) c[j]=1;
       else c[j]=0;
       }
还是过不了样例!~~
2009-08-05 00:03
hewenhao
Rank: 1
等 级:新手上路
帖 子:46
专家分:0
注 册:2007-1-10
收藏
得分:0 
回复 4楼 huicpc0876
用debug跟一下吧

2009-08-05 00:12
godbless
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:216
专家分:950
注 册:2009-7-24
收藏
得分:0 
回复 4楼 huicpc0876
改了后可以完整运行,只是你后半部分的算法有问题
2009-08-05 00:22
godbless
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:216
专家分:950
注 册:2009-7-24
收藏
得分:15 
第一个改这个。。改成你后来写的
for(j=blen-1;j>=0;j--)
      {
      if(b[j]==a[0]) c[j]=1;
       else c[j]=0;
       }
第二个 for(t=0;t<=blen-1;t++)  改成 for(t=0;t<=blen-1&&!flag;t++)

第三个
for(i=t;t<blen;t++)              //for(i=0,t--;t<blen;t++)              
         {printf("%c",b[t]);}    //   {printf("%c",b[t]);i++;}
         
          printf(" %d\n",i+1);   //    printf(" %d\n",i);

第三个或者改成
for(t--,i=t;t<blen;t++)
         {printf("%c",b[t]);}
         
          printf(" %d\n",blen-i);

[[it] 本帖最后由 godbless 于 2009-8-5 00:39 编辑 [/it]]
2009-08-05 00:30
tance123
Rank: 2
等 级:论坛游民
帖 子:33
专家分:48
注 册:2009-7-31
收藏
得分:0 
那么复杂
2009-08-05 08:38
huicpc0876
Rank: 2
等 级:论坛游民
帖 子:69
专家分:50
注 册:2009-7-24
收藏
得分:0 
回复 3楼 hewenhao
没有吧,我由前往后找,找到第一个满足的肯定是最长的啊 。
2009-08-05 10:09
紫ing~
Rank: 4
来 自:中科大
等 级:业余侠客
帖 子:103
专家分:273
注 册:2008-11-25
收藏
得分:5 
我写了一个简单点的,也能满足lz的要求,找到最长匹配的字符串,谨供参考。。。。
程序代码:
/*string match*/
#include "stdio.h"
#include "string.h"
void match(char *p,char *q)
{ while(strlen(p)>strlen(q))
    *(p+strlen(p)-1)='\0';
  while(strlen(p)<strlen(q))
    q=q+1;
  while(strcmp(p,q)!=0&&*p)
    {
     *(p+strlen(p)-1)='\0';
     q=q+1;
    }
  if(*p) printf("%d %s",strlen(p),p);
  else printf("NO match");
}

main()
{ char p[20],q[20];
  printf("Input p q:\n");
  gets(p);
  gets(q);
  match(p,q);
}

唯有天道恒在,往复循环,不曾更改。。。
2009-08-05 21:11
快速回复:求教,字符串最长的前后缀匹配
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.050600 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved