/**//* 一个文本串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; }
|