本文共 852 字，大约阅读时间需要 2 分钟。

题目：

我有两个表，表上面有N个指针，各有角度，然后问这两个表是否可以完全匹配

思路：

其实就是kmp的板题，不过稍有变化，需要进行三步。

1.对角度进行排序，然后处理出来前后的差值，因为这个表示可以旋转的，只要差值相同，那么就意味着表是可以匹配的

2.现在就需要求两个差值数列是否可以匹配，因为可以旋转，所以b数列可以从a数列的任意位置开始匹配，然后转一圈从头匹配，这样不太方便，于是把a数组复制一遍，这样就可以直接用b数组去匹配两倍的a数组，满足了b数组从各个位置匹配a数组都能匹配得到。

代码：

/*by kzl*/#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int maxx = 1e6+500;const int INF = 0x3f3f3f3f;typedef long long LL;int a[maxx],b[maxx],fail[maxx];int n;void getfail(int len){ int i=0,j=-1; fail[0] = -1; while(i!=len){ if(j==-1||b[i]==b[j]){ fail[++i] = ++j; } else{ j = fail[j]; } }}bool getindex(int len,int len2){ int i=0,j=0; while(i!=len){ if(j==-1||a[i]==b[j]){ i++;j++; if(j==len2)return true; } else{ j = fail[j]; } } return false;}int main(){scanf("%d",&n);for(int i=0;i
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/lwgkzl/article/details/82534706 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！