空间有形 梦想无限

找出字符串中最长连续重复字符串，重复次数一样情况下，重复单元长的优先，重复单元长度一样情况下排在前面的优先，举例如下

null->null
“”  -> ""
ab -> ab
aab -> a
aabbbc->b
aabbc->a
aa1212bc->12

 我的代码如下，有点抽象哦

主函数入口 public string FindMostContinuouslyRepeatedString(string s)

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;


using PuzzleInterface;

namespace PuzzleSolution
{
    class CharPosInfo
    {
        public LinkedList<int> PosList;
        public LinkedListNode<int> CurBegNode;
        public CharPosInfo()
        {
            PosList = new LinkedList<int>();
            CurBegNode = null; ;
        }

    };
    class CharPosTable
    {
        public CharPosInfo[] table;
        public int Count;
        public CharPosTable(string s)
        {
            table = new CharPosInfo[256];
            Count = s.Length;
            for (int i = 0; i < 256; i++)
            {
                table[(char)i] = new CharPosInfo();
            }
            char curCh;
            for (int i = 0; i < Count; i++)
            {
                curCh = s[i];
                table[curCh].PosList.AddLast(i);
            }
            for (int i = 0; i < 256; i++)
            {
                table[(char)i].CurBegNode = table[(char)i].PosList.First;
            }
        }
        public void SetRepeat(string s, ref Repeat rp,int begPos)
        {
            int startPos; int posOver,posStart;
            char ch; int v;
            LinkedListNode<int> node;
            LinkedListNode<int> rmNode;

            for (int k = 0; k < rp.ItemLen; k++)
            {
                 startPos = rp.PosInSrc + k;
                 ch = s[startPos];
                 CharPosInfo cpInfo = table[ch];
                 LinkedList<int> tList = cpInfo.PosList;
     
                node = cpInfo.CurBegNode.Next.Next;
                posOver = (startPos) + rp.ItemLen * (rp.Times - 1);
                posStart=startPos + rp.ItemLen;
                while (node != null)
                {
                     v = node.Value;
                    if (v >= posOver)
                    {
                        break;
                    }
   
                    {
                        if ( v<= begPos )
                        {
                            cpInfo.CurBegNode = node;

                        }
                        if (v <= posStart)
                        {
                            node = node.Next;
                            continue;
                        }
                        rmNode = node;
                        node = node.Next;
                        tList.Remove(rmNode);

                    }


                };
            }

        }
        public int FindNextCharPos(char c, ref LinkedListNode<int> cNode, int curPos ,int leastPos)
        {
 
            while (true)
            {
                if (cNode.Next != null)
                {
         
                    if (cNode.Next.Value <= curPos)
                    {
                        cNode = cNode.Next;
                        continue;
                    }
                    if (curPos  >leastPos)
                    {      
                        return -2;
                    }

                    return cNode.Next.Value;
                }
                else
                {
                    cNode = cNode.Next;
                    return -1;
                }
            }
        }

    }
   public  struct Repeat
    {
       public int Times;
       public int ItemLen;
       public int PosInSrc;
       public void Clear(){
           Times = 0;
           ItemLen = 0;
           PosInSrc = -1;
       }
    }


    public class Solution : IPatternRepetition
    {
        public static bool  StrEqual(string sA, int oA, string sB, int oB, int len)
        {
      
            for (int i=0; i < len; i++)
            {
                if (sA[oA + i] != sB[oB + i])
                {
                    return false;
                }
            }
            return true;

        }

        public static void GetRepeat(string s ,int sOffset, int nextOffset,ref Repeat rp)
        {
        //    Repeat rp = new Repeat();
            rp.Times = 1;
            rp.ItemLen = nextOffset - sOffset;
            rp.PosInSrc = sOffset;
            int slen = s.Length;
            int step = nextOffset;
            int stepOver =slen -rp.ItemLen;
            while (step <= stepOver)
            {
                if (StrEqual(s, sOffset, s, step, rp.ItemLen))
                {
                    rp.Times++;
                    step += rp.ItemLen;
                }
                else
                {
                    break;
                }
            }
        }
        public string FindMostContinuouslyRepeatedString(string s)
        {
            if (s == null ) return s;
            CharPosTable posTable = new CharPosTable(s);
            int slen = s.Length;
            if (slen < 2) return s;
            Repeat maxRepeat = new Repeat();
            maxRepeat.ItemLen = 1;  maxRepeat.PosInSrc = 0;  maxRepeat.Times = 1;
            char ch;
            Repeat rp = new Repeat();
            LinkedListNode<int> cNode;
            for (int i=0; i < slen; i++)
            {
                ch = s[i];
                int curPos = i;
                cNode = posTable.table[ch].CurBegNode;
                while (cNode!=null)
                {
                    curPos = posTable.FindNextCharPos(ch, ref cNode, curPos,
                        ((slen - i) / maxRepeat.Times  + i));
                    if (curPos == -2) {
                        break;
                    }
                    rp.Clear();
                    if (curPos == -1)
                    {
                        rp.Times=1;
                        rp.ItemLen = s.Length - i;
                        rp.PosInSrc = i;
                    }
                    else
                    {
                        GetRepeat(s, i, curPos, ref rp);
                    }
                    if(rp.Times>2)  posTable.SetRepeat(s, ref rp,i);
                    if (rp.Times > maxRepeat.Times)
                    {
                        maxRepeat = rp;
                        continue;
                    }
                    if ((rp.Times == maxRepeat.Times) && (rp.ItemLen > maxRepeat.ItemLen))
                    {
                        maxRepeat = rp;
                    }
                   
                }
            }
            if (maxRepeat.PosInSrc >= 0)
            {    //    System.Console.WriteLine("Real:"+maxRepeat.Times + " " + s.Substring(maxRepeat.PosInSrc, maxRepeat.ItemLen /* maxRepeat.Times*/));
                return s.Substring(maxRepeat.PosInSrc, maxRepeat.ItemLen /* maxRepeat.Times*/);
            }
            return null;

        }
    }
}
 

公司内部的Puzzle活动，我提交的代码（原代码速度第二，这个是事后修改了一点，比第一快乐一点）

福建 龙岩 永定 南开 酷讯 微软 搜索 广告 推荐 IM 网络应用 技术研发，工程管理 音乐 旅游 IPhone

• 主页面
• 文章汇整
• 文件夹
• 网站链接

• ace(not acer:)) layer
• 爱体(理疗)健康的经营情况
• 博客阅读后感 从ACE到其它
• Can you do it better?
• 招什么样的人
• B2C网站的服务观念太差了
• 回忆：我为什么高考没有报计算机系
• html内联图像协议
• c++ coding style
• 三亚蜈支洲岛 照片
• Training Windows Internal Architecture
• askfrom试用&兼IT人员颈肩腰腿背不适亚健康情况调查
• 你穷就让你买贵的
• 搜索引擎一二三流
• 从基本面出发

最新评论

• zihui: 不错
• onebird: 补上一个小作品 www.it-care.cn这个简单的网站是完全基于django的
• tito: 那如何分情况来判断是否需要造轮子呢?
• onebird: 主要是价格透明 便宜。 具备这个核心价值。
• bluetent: 核心员工要期望值高的，但我不建议所有人都很“牛”。 接下来一个很重要的问题就是：如何让所有员工都能实现价值，并得到尊重。 这个问题可能会逼迫我们搞愚民政策，让大家安...
• ppip: 不知道为什么。但是口碑却不错。
• onebird: Directory Listing Denied This Virtual Directory does not allow contents to be listed.
• onebird: ACE homepage http://www.cs.wustl.edu/~schmidt/ACE.html 我其实先看的twisted
• onebird: 是建军吗？ 好久不见 看你的文字觉得你变化不少 我的msn是nkzym _at_ hotmail.com 电话是131414加53627 <...
• ZHANG JIANJUN: 呵呵，习惯就好。大部分的b2c的服务还没能达到24小时啦：） 刚才一口气看了你大半年的日志， 这么些年了，还是这么自律啊：） 哈哈，搞得我都快被你激励...

• 生活 [59]
• 技术 [52]
• 学习 [10]
• 互联网 [42]
• 心情 [11]
• 工作 [37]
• 工程 [5]
• 关于我 [2]
• 一般分类 [2]
• 代码 [9]
• 作品 [0]
• 设计 [0]
• 转贴 [0]

• RSS 0.90
• RSS 1.0
• RSS 2.0
• Atom