There are n strings with the length of no more than 100 characters. Can you find the longest continuous string section(ie. S(i)S(i+1)...S(j) and j-i+1 is maximaze) that all the letters appear even times.
There will be multiple test case. For each test: The first line has a positive number n(1 <= n <= 10000). Then followed n rows, each row has a string making up with lowercase letters.
Output the longest section(left, right),where left is the beginning loction of the section and right is the ending loction of the section. If there is more than one such section, output the one whose left is smallest.If there is none such section,just output "No one".
//
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<algorithm>using namespace std;const int maxn=10000+100;char str[300];struct Node{ int sum; int index;};Node g[maxn];bool cmp(Node h,Node k){ if(h.sum!=k.sum) return h.sum<k.sum; return h.index<k.index;}int main(){ int n; while(scanf("%d",&n)==1) { for(int i=0;i<=n;i++) g[i].sum=0,g[i].index=i; for(int i=1;i<=n;i++) { scanf("%s",str); int cnt=0; for(int j=0;str[j];j++) { cnt=cnt^(1<<(str[j]-'a')); } g[i].sum=g[i-1].sum^cnt; } sort(g,g+n+1,cmp); int flag=0,st=-1,ed=-1,_max=0; for(int i=0;i<n;) { if(g[i].sum==g[i+1].sum) { flag=1; int j=i+1; while(j<=n&&g[i].sum==g[j].sum) j++; int len=g[j-1].index-g[i].index; if(len>_max) _max=len,st=g[i].index,ed=g[j-1].index; else if(len==_max) { if(st>g[i].index) st=g[i].index,ed=g[j-1].index; } i=j; } else { i++; } } if(!flag) printf("No one/n"); else printf("%d %d/n",st+1,ed); } return 0;}
