<commit_before>package org.lotus.algorithm.strings;

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by quanchengyun on 2019/10/7.
 */
public class Strings {


    public static char[]  str= {'a','b','c','d','e','f','g','h'};

    private static  char[] getStr(){
        return Arrays.copyOf(str,str.length);
    }
    //1.start-----------------------------------------------------------
    /**
     * 在原字符串中把字符串尾部的m个字符移动到字符串的头部，
     * 要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。
     * 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。
     *
     * ： (x~y~)~=y~~x~~=yx
     */
    public  static void  revertChar(char[] str , int m){
            //0,n-1
            //x= str[0],str[n-1-m] , y = n-1-m+1 , n-1
            if(m>=str.length){
                System.out.print("invalid param m");
            }
           revert(str,0,str.length-1-m);
           revert(str,str.length-m,str.length-1);
           revert(str,0,str.length-1);
           System.out.println(str);
    }

    private static void  revert(char[] str , int start ,int end){
        int j=start;
        int k=end;
        while(j < k){
            char v = str[j];
            str[j]=str[k];
            str[k]= v;
            j++;
            k--;
        }
    }

    @Test
    public void testRevert(){
        revertChar(getStr(),3);
        revertChar(getStr(),4);
        revertChar(getStr(),5);
    }

    /**
     *单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。
     * 为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”
     *  (x~_y~_z~)~ = z~~_y~~_x~~ = z_y_x
     */
    private static void revertWord(){
        //略
    }
    //1.end-----------------------------------------------------------



}<commit_msg>commit<commit_after>package org.lotus.algorithm.strings;

import org.junit.Test;

import java.util.Arrays;

/**
 * Created by quanchengyun on 2019/10/7.
 */
public class Strings {


    public static char[]  str= {'a','b','c','d','e','f','g','h'};

    private static  char[] getStr(){
        return Arrays.copyOf(str,str.length);
    }
    //1.start-----------------------------------------------------------
    /**
     * 在原字符串中把字符串尾部的m个字符移动到字符串的头部，
     * 要求：长度为n的字符串操作时间复杂度为O(n)，空间复杂度为O(1)。
     * 例如，原字符串为”Ilovebaofeng”，m=7，输出结果为：”baofengIlove”。
     *
     * ： (x~y~)~=y~~x~~=yx
     */
    public  static void  revertChar(char[] str , int m){
            //0,n-1
            //x= str[0],str[n-1-m] , y = n-1-m+1 , n-1
            if(m>=str.length){
                System.out.print("invalid param m");
            }
           revert(str,0,str.length-1-m);
           revert(str,str.length-m,str.length-1);
           revert(str,0,str.length-1);
           System.out.println(str);
    }

    private static void  revert(char[] str , int start ,int end){
        int j=start;
        int k=end;
        while(j < k){
            char v = str[j];
            str[j]=str[k];
            str[k]= v;
            j++;
            k--;
        }
    }

    @Test
    public void testRevert(){
        revertChar(getStr(),3);
        revertChar(getStr(),4);
        revertChar(getStr(),5);
    }

    /**
     *单词翻转。输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变，句子中单词以空格符隔开。
     * 为简单起见，标点符号和普通字母一样处理。例如，输入“I am a student.”，则输出“student. a am I”
     *  (x~_y~_z~)~ = z~~_y~~_x~~ = z_y_x
     */
    private static void revertWord(){
        //略
    }
    //1.end-----------------------------------------------------------



    //2.start------------------------------------------------------------
    /**
     * 最长回文子串问题 ,
     * 1.manacher 算法 ，扩展字符数组填充特殊字符# ，2N-1
     * 2. 以i为中心扩展查找
     */

    private static void palindromic(char[] str){
        char[] extend = new char[str.length*2-1];
        for(int i=0,j=0;i<str.length;i++,j++){
            extend[j]=str[i];
            j++;
            if (j<extend.length)
                extend[j]='#';
        }

        int[] mp = new int[extend.length];

        int m=0,r=0;
        for(int i=0;i<extend.length;i++){
            mp[i]= i < r ? Math.min(mp[2*m-i],r-i):1;
            while(i-mp[i]>=0 && i+mp[i]<extend.length && extend[i-mp[i]]==extend[i+mp[i]]){
                mp[i]++;
            }
            //i为中心的构成回文，如果i大于等于 r ,那么扩展后 r=i,m=i
            if(i+mp[i] > r) {
                r=i+mp[i]-1;
                m=i;
            }
        }
        //找到最大的那一个
        int max=0;
        for(int i=0;i<mp.length;i++){
            if (mp[i]>mp[max]){
                max=i;
            }
        }
        if (mp[max]>1) {
            int left = max-mp[max]+1;
            int right = max+mp[max]-1;
            left = (left+1)/2;
            right = (right-1)/2;
            for (int i=left;i<=right;i++){
                System.out.print(str[i]);
            }
        }
    }

    @Test
    public void testPalindromic(){
        char[] origin = "abcdeffeffedcab".toCharArray();
        palindromic(origin);
    }

    //2. end------------------------------





}
{'fraction_non_alphanumeric': 0.23381877022653721, 'fraction_numerical': 0.015776699029126214, 'mean_word_length': 1.384281581485053, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '936997', 'n_tokens_mistral': 2008, 'n_tokens_neox': 2068, 'n_words': 278}