 /**//*
一个文本串len<=10^5
n<=10个boring串,len<=10
求最长的连续子串,不包含任何一个boring串

我之前的做法比较慢
先用strstr预处理出所有文本串中所有boring段
接着对文本串从左到右枚举起始位置i,
然后找[i,n]中那些boring段中右端点最左的位置j,则[i,j)肯定不包含boring串的
更新答案pos = i, len = j-i
而“找[i,n]中那些boring段中右端点最左的位置j”可用线段树做
即对一个点i,存一个最小的值j,表示[i,j]是boring串,没有的话令j=N+1,N为文本串长度
O(NlogN + nN)吧

看了别人的,用类似dp的做法
令dp[i] = dp[i-1]+1,然后检查有没boring串(以i为结尾)
有的话,置为min{boring[i]}-1 不是置零!!!
O(10nN)吧
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const int MAXN = 100086;
const int INF = 1000000000;

char str[MAXN], boring[20];
int Min[MAXN*4];

 void insert(int p, int l, int r, int pos, int val) {
Min[p] = min(Min[p], val);
 if(l==r) {
return;
}
int m = (l+r)>>1;
 if(pos <= m) {
insert(p<<1, l, m, pos, val);
}
 else {
insert(p<<1|1, m+1, r, pos, val);
}
}

 int query(int p, int l, int r, int left , int right) {
 if(left <= l && r <= right) {
return Min[p];
}
int m = (l+r)>>1, ans = INF;
 if(left <= m) {
ans = min(ans, query(p<<1, l, m, left, right));
}
 if(m < right) {
ans = min(ans, query(p<<1|1, m+1, r, left, right));
}
return ans;

}


int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
#endif
 for(; ~scanf("%s",str+1); ) {
int n, N = strlen(str+1);
scanf("%d", &n);
 /**//*
fill(Min, Min + 4*N, N+1);
for (int i = 0; i <n ; i++) {
scanf("%s", boring);
int len = strlen(boring);
char *p = str+1;
while((p = strstr(p, boring)) != NULL) {
int pos = p - str;
insert(1, 1, N, pos, pos+len-1);
p ++;
}
}
int len = 0, pos = 0;
for (int i = 1; i<=N; i++) {
int next = query(1, 1, N, i, N);
if(next - i > len) {
len = next - i;
pos = i - 1;
}
}
*/
int len = 0, pos = 0;
char boring[10][20];
int len_boring[10];
 for(int i = 0; i < n; i ++) {
scanf("%s", boring[i]);
len_boring[i] = strlen(boring[i]);
}
int l = 0;
 for (int i = 1; i <= N; i ++) {
l++;//dp[i] = dp[i-1] +1;
bool flag = false;
 for(int j = 0; j < n; j++) {
 if(i < len_boring[j]) {
continue;
}
int k = 0, t = len_boring[j] - 1;
 for (; k < len_boring[j]; k++, t--) {
 if(boring[j][t] != str[i-k]) {
break;
}
}
 if(t < 0) {
l = min(len_boring[j]-1, l);//不是置零
}
}
 if(l > len) {
len = l;
pos = i - l;
}
}
printf("%d %d\n", len, pos);
}
return 0;
}


|