Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3080 Blue Jeans---KMP

Posted on 2009-10-13 22:46 Uriel 阅读(840) 评论(0)  编辑 收藏 引用 所属分类: POJ字符串处理
      后缀数组还是没懂。。Regional之前应该是来不及了。。
      这题可以练后缀数组的。。KMP水过去了。。后来发现strstr也行。。跟KMP一样16Ms。。。
    
strstr版本:
/*Problem: 3080  User: Uriel 
   Memory: 584K  Time: 16MS 
   Language: G++  Result: Accepted
*/
 

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

using namespace std;

int start,n;
char str[15][100];

struct P
{
    
char res[100];
}
Ans[100];

char dest[100];
int Next[100];

bool cmp(P a,P b)
{
    
return strcmp(a.res,b.res)<0;
}


void Sov()
{
    
int i;   
    
for(i=1;i<n;i++)
    
{        
        
if(strstr(str[i],dest)==NULL)
        
{
            start
=1;
            
return ;
        }

    }

    
return ;
}
   

int main()
{
    
int t,i,j,k,s;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        memset(str,
0x00,sizeof(str));
        
for(i=0;i<n;i++)
        
{
            scanf(
"%s",str[i]);
        }

        s
=0;
        
for(i=60;i>=3;i--)
        
{
            j
=0;
            
while(j+i<=60)
            
{
                start
=0;
                memset(dest,
0x00,sizeof(dest));
                strncpy(dest,
&str[0][j],i);
                Sov();
                
if(!start)
                
{
                    strcpy(Ans[s
++].res,dest);
                }

                j
++;
            }

            
if(s)break;
        }

        
if(s)
        
{
            sort(Ans,Ans
+s,cmp);
            printf(
"%s\n",Ans[0].res);
        }

        
else
        
{
            printf(
"no significant commonalities\n");
        }

    }

    
return 0;
}


KMP版本:
/*Problem: 3080  User: Gilhirith 
   Memory: 584K  Time: 16MS 
   Language: G++  Result: Accepted
*/
 

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

using namespace std;

int start,n;
char str[15][100];
char dest[100];
int Next[100];

struct P
{
    
char res[100];
}
Ans[100];

int GetNextVal(char* Pattern, int next[])
{
   
int i=1,j=0;
   
int p_len=strlen(Pattern);
   next[
0]=0;
   
while(i<p_len)
   
{
      
if(Pattern[i]==Pattern[j])
      
{
         next[i]
=j+1;
         i
++;
         j
++;
      }

      
else if(j>0)
      
{
          j
=next[j-1];
      }

      
else
      
{
          next[i]
=0;
          i
++;
      }

  }

  
return 0;
}


int kmpMatch(char* Src, char* Pattern, int pos)
{
    
int i=pos,j=0;
    
int s_len,p_len;
     s_len
=strlen(Src);
      p_len
=strlen(Pattern);
      
while(i<s_len)
      
{
        
if(Src[i]==Pattern[j])
         
{
          
if(j==p_len-1)return i-p_len+1;
          i
++;
          j
++;
        }

        
else if(j>0)
        
{
            j
=Next[j-1];
        }

        
else
            i
++;
    }

    
return -1;
}


bool cmp(P a,P b)
{
    
return strcmp(a.res,b.res)<0;
}


void Sov()
{
    
int i;   
    
for(i=1;i<n;i++)
    
{        
        
if(kmpMatch(str[i], dest, 0)==-1)
        
{
            start
=1;
            
return ;
        }

    }

    
return ;
}
   

int main()
{
    
int t,i,j,k,s;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        
for(i=0;i<n;i++)
        
{
            scanf(
"%s",str[i]);
        }

        s
=0;
        
for(i=60;i>=3;i--)
        
{
            j
=0;
            
while(j+i<=60)
            
{
                start
=0;
                memset(dest,
0x00,sizeof(dest));
                strncpy(dest,
&str[0][j],i);
                GetNextVal(dest,Next);
                Sov();
                
if(!start)
                
{
                    strcpy(Ans[s
++].res,dest);
                }

                j
++;
            }

            
if(s)break;
        }

        
if(s)
        
{
            sort(Ans,Ans
+s,cmp);
            printf(
"%s\n",Ans[0].res);
        }

        
else
        
{
            printf(
"no significant commonalities\n");
        }

    }

    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理