### Kino's blog

By Kino, history, 3 years ago, ,

can anyone give me some link to kopeliovich_diploma translation in englich or to some tutorial of the same ideas proposed for serguei kopeliovich?

• +6

By Kino, 5 years ago, ,

please god of code, do not make me wait 9 days by a contest of codeforces

• +57

By Kino, 5 years ago, ,

hello everyone, i want to study flow and its aplications, i already knows the basics, can anyone suggest me some literature and some problems, thanks

• 0

By Kino, 5 years ago, ,

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;
}