zoj 3296 Connecting the Segments

zoj 3296 Connecting the Segments

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define M 100050char str1[M],str[2*M];int rad[M],nn,n;struct st{    int s,t;}a[100010];int cmp(const st &b,const st &c){    if(b.s<c.s)    {        return 1;    }    return 0;}void Manacher(int *rad,char *str,int n){    int i;    int mx = 0;    int id;    for(i=1; i<n; i++)    {        if( mx > i ) rad[i] = rad[2*id-i]<mx-i?rad[2*id-i]:mx-i;     else rad[i] = 1;        for(; str[i+rad[i]] == str[i-rad[i]]; rad[i]++) ;        if( rad[i] + i > mx )        { mx = rad[i] + i; id = i;        }    }}int main(){    int i,ans,Case=1,j;    while(scanf("%s",str1)!=EOF)    {        nn=strlen(str1);        n=2*nn+2;        str[0]='$';        for(i=0;i<=nn;i++)        { str[2*i+1]='#'; str[2*i+2]=str1[i];        }         Manacher(rad,str,n);        ans=1;        int k=0;        for(i=2;i<=n;i++)        { rad[i]--; if(rad[i]==0)     continue; if(str[i]=='#') {     if((rad[i])%2==1)     {         a[++k].s=(i-(rad[i]))/2;         a[k].t=(i+(rad[i]))/2;     }     else     {         a[++k].s=(i-(rad[i])+1)/2;         a[k].t=(i+(rad[i])-1)/2;     } } else if(str[i]>='a'&&str[i]<='z') {     if((rad[i])%2==0)     {         a[++k].s=(i-(rad[i]))/2;         a[k].t=(i+(rad[i]))/2;     }     else     {         a[++k].s=(i-(rad[i])+1)/2;         a[k].t=(i+(rad[i])-1)/2;     } }        }        sort(a+1,a+k+1,cmp);        int end=0,sta=1,sum=1;        i=1;        while(i<=k&&a[i].s==sta)        { if(a[i].t>end)     end=a[i].t; i++;        }        while(end!=nn)        { sta=end+1; j=end; while(i<=k&&a[i].s<=sta) {     if(a[i].t>j)         j=a[i].t;     i++; } end=j; sum++;        }        printf("%dn",sum-1);    }    return 0;}