Cod sursa(job #1461556)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 15 iulie 2015 22:56:19
Problema Potrivirea sirurilor Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.17 kb
package infoarenajava;

import java.io.*;


class InfoArenaJava {

    
    public static void main(String[] args) throws IOException {
        
        String cuv = null,str= null,rand= "";
        int[] t=new int[2000005];
        int i=0,suma=0;
        
       
            BufferedReader in= new BufferedReader(new FileReader("strmatch.in"));
            cuv=in.readLine();
            str=in.readLine();
        
        
        tabla(t,cuv);
        
        do{
                i= srch(i,str,cuv,t);
                if(i < str.length())
                {
                    rand= rand+ new String(i+" ");
                    suma++;
                }
                i++;
                
        
        }while(i < str.length());
        
        
            
        BufferedWriter out= new BufferedWriter(new FileWriter("strmatch.out"));
        out.write(String.valueOf(suma));
        out.flush();
        out.newLine();
        out.write(rand);
        out.flush();
        
    }
    
    public static void tabla(int[] t,String cuv){
        
        int pos=2,cnd=0;
        
        t[0]=-1;
        t[1]=0;
        
        while( pos < cuv.length() )
            if(cuv.charAt(pos-1) == cuv.charAt(cnd))
            {
                cnd++;
                t[pos]=cnd;
                pos++;
            }
            else if( cnd > 0 )
            {
                cnd=t[cnd];
            }
            else
            {
                t[pos]=0;
                pos++;
            }
        
    }
    
    public static int srch(int m,String str,String cuv,int[] t){
        
        int i=0;
        
        while( (m+i) < str.length() )
            if(str.charAt(m+i) == cuv.charAt(i))
            {
                if(i == cuv.length()-1)
                    return m;
                i++;
            }
            else
                if(t[i]>-1)
                {
                    m= m+i-t[i];
                    i= t[i];
                }
                else
                {
                    m= m+1;
                    i= 0;
                }
        return str.length();
    }
}