循环单词问题

怼烎@ 2022-05-15 12:36 150阅读 0赞

# 一，问题描述： #

1，如果一个单词通过循环右移获得的单词，我们称这些单词都为一种循环单词。例如：picture和turepic就是属于同一种循环单词。现在给出n个单词，需要统计这n个单词中有多少种循环单词。

2，输入格式：  
(1) 输入包括n+1行；  
(2) 第一行为单词个数n(1<=n<=50)  
(3) 接下来的n行，每行一个单词word\[i\]，长度length(1 ≤ length ≤ 50)。由小写字母构成

3，输出描述：  
输出循环单词的种数

4，输入例子

5  
picture  
turepic  
icturep  
word  
ordw

5,，输出例子

# 二、算法实现 #

import java.util.*;
    /** * 求循环单词 * @author superman * */
    public class Main2{ 
    
        public static void main(String []args)
        {
            Scanner scan=new Scanner(System.in);
            while(scan.hasNext())
            {
                int n=scan.nextInt();
                String []strs=new String[n];
                for(int i=0;i<n;i++)
                {
                    strs[i]=scan.next();
                }
    
                int sum=xunhuan(strs);
    
                System.out.println(sum);
            }
        }
    
        public static int xunhuan(String []strs)
        {
    
            int sum=0;
            int temp=0;
            List<String> list=new ArrayList<String>();//使用集合来存储字符串
    
            for(int i=0;i<strs.length;i++)
            {
                Iterator<String> it=list.iterator();
                while(it.hasNext())
                {
                    if(Judgesame(strs[i],(String)it.next()))
                    {
                        temp=1;  //如果相同的话，直接把temp=1
                        break;
                    }
                }
    
                if(temp!=1)  //temp不等于1,说明该字符串在集合中是不存在，之前没有存储过的。
                {
                    sum++;
                    list.add(strs[i]);
                }
                else
                {
                    temp=0;
                }
            }
    
            return sum;
        }
    
        public static boolean Judgesame(String left, String right)//判断两个字符串是否相同
        {
            int len1=left.length();
            int len2=right.length();
    
            if(left==null||len1==0||right==null||len2==0)
            {
                return false;
            }
            if(len1!=len2)
            {
                return false;
            }
    
            String str=right.concat(right); //把right字符串连接到right字符串。就变成两倍长的right
    
            if(str.contains(left))  //然后检查一下长字符串包含了短字符串
            {
                return true;
            }else
            {
                return false;
            }
        }
    }

![这里写图片描述][70]

import java.util.*;
    
    /** * n个单词中有多少种循环单词 * @author superman * */
    public class Main { 
        //获得循环单词的种数
        public static int getCycleWordNum( HashMap <Integer,String>map) {
            int sum=0;
            int res=0;
            while(!isAllNull(map)) {
                int t=map.size();
                while(map.get(t)==null) {
                    t--;
                }
                String temp= map.get(t);
                String result=temp+temp;
    
                for(int key:map.keySet()) {
                    if((map.get(key)!=null)&&(getIndex(result,map.get(key))!=-1)) {
                        res=1;
                        map.put(key, null);
                    }
                }
                sum+=res;
                res=0;
            }
    
            return sum;
        }
    
      //判断所有的数是否操作过
      public static boolean isAllNull(HashMap<Integer,String>map) {
          for(int  key:map.keySet()) {
              if(map.get(key)!=null)
                  return false;
          }
          return true;
      }
      //KMP算法
       public static int getIndex(String s,String m) {
            if(s==null||s.length()==0)
                return 0;
            char[]ss=s.toCharArray();
            char[]sm=m.toCharArray();
            int si=0;
            int mi=0;
            int[]next=next(sm);
            while(mi<sm.length&&si<ss.length) {
    
                if(ss[si]==sm[mi]) {
                    si++;
                    mi++;
                }else if(next[mi]==-1) {
    
                    si++;               
                }else {
                    mi=next[mi];
                }
    
            }
    
            return mi==sm.length?si-mi:-1;
        }
    
        //鑾峰緱next鏁扮粍
        public static int[] next(char[]m){
            if(m.length==1) {
    
                return new int[] {
       1};
            }
            int[]next=new int[m.length];
            next[0]=-1;
            next[1]=0;
            int pos=2;
            int cn=0;
            while(pos<m.length) {
                if(next[pos-1]==next[cn]) {
                    next[pos++]=++cn;
                }else if(cn>0) {
                    cn=next[cn];
                }else {
                    next[pos++]=0;
                }   
            }
    
            return next;
        }
    
        public static void main(String[] args) {
         HashMap <Integer,String>Map=new HashMap<>();
         Scanner sin =new Scanner(System.in);
         while(sin.hasNext()) {
             int n=Integer.parseInt(sin.nextLine());
             while(n!=0) {
                 Map.put(n,sin.nextLine());
                 --n;
             }
             System.out.println(getCycleWordNum(Map));
         }
    
     }
    }

[70]: /images/20220515/d37798d48de84fea90e00f9e2ab4a104.png