[KMP字符串子串匹配,减枝] Bazinga

题意：给出n个串 求最大的n使 前n-1个串不全是他的子串
不知道为什么写的kmp被T了
这里用strstr过的。
strstr(m,n)函数如果n是m的子串返回在m中的第一个字符的地址 else NULL 注意如果匹配过得串就不必匹配了，因为他已经是别的串的子串了

主函数部分：(剪枝)

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int main()
{
   
	int t;
	scanf("%d", &t);
	for(int cas=1; cas<=t; cas++) {
   
		memset(vis,0,sizeof(vis));
		int n;
		scanf("%d", &n);
		int flag=0;
		for(int i=1; i<=n; i++) {
   
			scanf("%s", s[i]);
			for(int j=i-1; j>=1; j--) {
   
				if(vis[i]) continue;
				if(strstr(s[i],s[j])==NULL) flag=i;
				else vis[j]=1;
			}
		}
		if(!flag) {
   
			printf("Case #%d: -1\n",cas);
		}
		else {
   
			printf("Case #%d: %d\n",cas,flag);
		}
	}
	return 0;
}

kmp做法(主函数部分一样的)
KMP算法：
https://blog.csdn.net/f1033774377/article/details/82556438

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int N=2007;
char s[N][N];
int vis[N];
//kmp函数 
void getf(int *F,char *B)
{
   
	F[0]=-1;
	int m=strlen(B);
	for (int i=1;i<m;i++)
	{
   
	    int j=F[i-1];
	    while ((B[j+1]!=B[i])&&(j>=0))
	        j=F[j];
	    if (B[j+1]==B[i])
	        F[i]=j+1;
	    else
	        F[i]=-1;
	}	
}
int kmp(char *A, char *B)
{
   
	int F[N];
	getf(F,B);
	int n=strlen(A);
	int m=strlen(B);
	int i=0, j=0;
	while (i<n)
	{
   
	    if (A[i]==B[j])
	    {
   
	        i++;
	        j++;
	        if (j==m)
	        {
   
	            return i-m;
	        }
	    }
	    else
	    {
   
	        if (j==0)
            	i++;
        	else
            	j=F[j-1]+1;
	    }
	}
	return -1;
}


int main()
{
   
	int t;
	scanf("%d", &t);
	for(int cas=1; cas<=t; cas++) {
   
		memset(vis,0,sizeof(vis));
		int n;
		scanf("%d", &n);
		int flag=0;
		for(int i=1; i<=n; i++) {
   
			scanf("%s", s[i]);
			for(int j=i-1; j>=1; j--) {
   
				if(vis[i]) continue;
				if(kmp(s[i],s[j])==-1) flag=i;
				else vis[j]=1;
			}
		}
		if(!flag) {
   
			printf("Case #%d: -1\n",cas);
		}
		else {
   
			printf("Case #%d: %d\n",cas,flag);
		}
	}
	return 0;
}