Kino's blog

By Kino, 9 years ago, In English

problem link ----> here

this is my solution, i can´t find something better

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define sf scanf
#define pf printf
#define ll long long
#define MAXN 10002

int d1[MAXN];
int d2[MAXN];
int manager(char *s, int n){
    int cant=0;
    int l,l2,r,r2,k,i;
    l=l2=0; r=r2=-1;
    for(i=0;i<n;i++){
        k = (i>r ? 0 : min(d1[l+r-i],r-i)) + 1;
        while(i+k<n && i-k>=0 && s[i-k]==s[i+k]) k++;
        d1[i]=--k;
        if(i+k>r) l=i-k, r=i+k;
        k = (i>r2 ? 0 : min(d2[l2+r2-i+1],r2-i+1)) + 1;
        while( (i+k-1)<n && (i-k)>=0 && s[i+k-1]==s[i-k] ) ++k;
        d2[i]=--k;
        if( (i+k-1)>r2 ) l2=i-k, r2=i+k-1;
        cant+=(d1[i]+d2[i]);
    }
    return cant;
}

int K;
bool isP(int i,int j){
    int x = i + ((j-i+1)/2);
    return ((j-i+1)%2==0 ? (x-d2[x] <= i) : (x-d1[x] <= i) );
}

typedef pair<vector<int>,int> par;

par prefix_function(string s){
	int n = (int)s.length();
	vector<int> pi(n);
	int maxpi = 0;
	for(int i=1;i<n;i++){
		int j = pi[i-1];
		while(j>0 && s[i] != s[j])
            j = pi[j-1];
		if(s[i] == s[j]) j++;
		pi[i] = j;
		maxpi = max(maxpi,pi[i]);
	}
	return {pi,maxpi};
}

int solve(char *s, int n){//O(n^2)
    int ans = 0, maxpi = 0;
    vector<int> pi;
    string ss = "";
    for(int i = 0; i < n; i++){
        ss = s[i] + ss;

        par kmp = prefix_function(ss);//O(n)
        pi = kmp.first;
        maxpi = kmp.second;

        int aux = max(K-1,maxpi);
        aux++;
        //O(n)
        for(int j = i-aux+1, ind = aux-1 ; j>=0; j--,ind++){
            int yy = (ind+1) - pi[ind];//compresion_line
            if(isP(j,i) && yy < (ind+1))
                if( (yy == 1 && ind+1 >= 4) ||
                    ((ind+1) % yy == 0 && isP(i-yy+1,i)) )
                        ans++;
        }
    }
    return ans;
}


char w[MAXN];
int main(){
    sf("%d%s",&K,w);
    int n = strlen(w);
    manager(w,n);
    pf("%d\n",solve(w,n));

    return 0;
}
  • Vote: I like it
  • -23
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

such a wonderful trick to get downvotes