题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4749
题意:给出两个数字串A、B。问A中有多少不相交的子串a能匹配B。匹配的意思是a中任意两个位置i和j的大小关系和B的这两个位置的大小关系是一样的。
思路:若是完全一模一样的匹配的话那么KMP是很好理解的。那么对于上述的比较方式怎么比较两个串相等呢?对于a的位置i和B的位置i,我们只要比较i之前a中a[i]的个数和B中B[i]的个数是否相等,以及a中小于a[i]的个数和B中小于B[i]的数字个数是否相等。只要每个位置都满足则这两个串匹配。
int f[N][30],g[N][30],next[N]; int a[N],b[N],n,m,K; int visit[N]; int ok(int x,int y) { if(g[x][b[x]]!=g[y][b[y]]-g[y-x][b[y]]) return 0; int cnt1=0,cnt2=0,i; for(i=1;i<b[x];i++) cnt1+=g[x-1][i]; for(i=1;i<b[y];i++) cnt2+=g[y-1][i]; for(i=1;i<b[y];i++) cnt2-=g[y-x][i]; return cnt1==cnt2; } void getNext() { next[1]=0; int i,j=0; for(i=2;i<=m;i++) { while(j&&!ok(j+1,i)) j=next[j]; if(ok(j+1,i)) j++; next[i]=j; } } int ok1(int x,int y) { if(g[x][b[x]]!=f[y][a[y]]-f[y-x][a[y]]) return 0; int cnt1=0,cnt2=0,i; for(i=1;i<b[x];i++) cnt1+=g[x-1][i]; for(i=1;i<a[y];i++) cnt2+=f[y-1][i]; for(i=1;i<a[y];i++) cnt2-=f[y-x][i]; return cnt1==cnt2; } void kmp() { int i,j=0; for(i=1;i<=n;i++) { while(j&&!ok1(j+1,i)) j=next[j]; if(ok1(j+1,i)) j++; if(j==m) visit[i]=1,j=next[j]; } } int main() { while(cin>>n>>m>>K) { clr(f,0); clr(g,0); clr(visit,0); int i,j; FOR1(i,n) { RD(a[i]); FOR1(j,K) f[i][j]=f[i-1][j]; f[i][a[i]]++; } FOR1(i,m) { RD(b[i]); FOR1(j,K) g[i][j]=g[i-1][j]; g[i][b[i]]++; } getNext(); kmp(); int ans=0; i=1; while(i<=n) { if(visit[i]) i+=m,ans++; else i++; } PR(ans); } }