Coding/Python 삽질기2013. 5. 6. 00:43

KMP algorithm

def KMP_Preprocessing(pattern, nSize):

    pi = [0] * (nSize + 1)

    k = -1

    j = 0

    pi[j] = k

    

    while ( j < nSize ):

        if ( k == -1 or pattern[j] == pattern[k] ):

            j += 1

            k += 1

            pi[j] = k

        else:

            k = pi[k]

            

    return pi



def KMP_find(text, pattern, ppi):

    nSize = len(text)

    nPSize = len(pattern)

    i = 0

    j = 0


    while (i < nSize):

        if ( j == -1 or text[i] == pattern[j] ): 

            i += 1

            j += 1

        else:    

            j = ppi[j];


        if (j == nPSize):

            print i-j

            j = ppi[j];


strPattern = "ababababca"

strPattern_pi = KMP_Preprocessing(strPattern, len(strPattern) )


strString ="asdsadf9alkjababababcaasdf"

KMP_find(strString, strPattern, strPattern_pi)






저작자표시

'Coding > Python 삽질기' 카테고리의 다른 글

fibonacci 수열  (0) 2013.06.20
10000개의 겹치는 않는 좌표 만들기  (0) 2012.11.07
[Python] Undo / Redo 구현하기  (0) 2011.06.16
Posted by chobocho
Coding/Python 삽질기2012. 11. 7. 01:31

10000개의 겹치는 않는 좌표 만들기

#Python Version

import random

result = []

while ( len(result) < 10000 ):

    x = random.randint(1, 10001)

    y = random.randint(1, 10001)

    result.append( (x, y) )

    result = list(set(result))


/* C++ Version */
#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <set>
using namespace std;

typedef pair<int, int> Point2D;

class IsSame {
public:
       bool operator()(const Point2D &left, const Point2D &right) {
              return ((left.first < right.first) || ( (left.first == right.first) && (left.second < right.second)));
       }
};

void process();

int main() {
    process();
    return 0;
}

void process() {
    fstream target_fp;
    set<Point2D, IsSame> set_points;
    
    target_fp.open("input2.txt",ios::out);
    
    srand(time(NULL));
    
    int count = 10000; //rand()%10 + 1;
    int x = 0, y = 0;
  
    Point2D tempPoint;
   
    target_fp << count << endl;
 
    while ( set_points.size() < count) {
    x = rand()%10000;
    y = rand()%10000;
    tempPoint.first = x;
    tempPoint.second = y;
    set_points.insert(tempPoint);
    }
    set<Point2D, IsSame>::iterator it;
    for ( it = set_points.begin(); it != set_points.end(); it++ ) {
          if ( it != set_points.begin() ) {
            target_fp << endl;
          }
       target_fp << it->first << " " << it->second;
    }
        
    target_fp.close();
}


'Coding > Python 삽질기' 카테고리의 다른 글

KMP algorithm  (0) 2013.05.06
[Python] Undo / Redo 구현하기  (0) 2011.06.16
간단한 반복 작업 매크로  (0) 2011.01.12
Posted by chobocho
Coding/Python 삽질기2011. 6. 16. 01:17

[Python] Undo / Redo 구현하기

#-*- coding: cp949 -*-
#
# undo/redo 구현 방법
# 1) undo stack를 만든다.
# 2) redo stack를 만든다.
# 3) 새로운 액션을 undo에 넣는다.
# 4) 사용자가 undo를 선택하면 redo.append ( undo.pop() ) 를 수행한다.
# 5) 사용자가 redo를 선택하면 undo.append ( redo.pop() ) 를 수행한다.

undo = []
redo = []

undo.append (1)
undo.append (2)
undo.append (3)
redo.append ( undo.pop() )


print undo
print redo

'Coding > Python 삽질기' 카테고리의 다른 글

10000개의 겹치는 않는 좌표 만들기  (0) 2012.11.07
간단한 반복 작업 매크로  (0) 2011.01.12
http://www.pythonchallenge.com...Level6  (0) 2010.12.13
Posted by chobocho
Coding/Python 삽질기2011. 1. 12. 00:24

간단한 반복 작업 매크로

#-*- coding: cp949 -*-
# Name        : py_patten.py
# Author      : chobocho.com
# Version     :
# Copyright   :
# Description : simple number change 
#

from Tkinter import *
import tkMessageBox
 
save_file_name = "test.txt"
names = [ 'number1', 'number2' ]
table  = { names[0] : '100', names[1] : '200' } 

text_data = """Trees are  %(number1)s 
won,  %(number2)s won!""" 
 
class App:
    def __init__ (self, master):
    
        self.target_file_name = save_file_name
        
        frame = Frame(master)
        frame.pack()
        
        f3 = Frame(frame, width = 100, height = 40)
        f3.grid(row = 0, column = 0)
        
        self.label_1 = Label(f3, text= names[0])
        self.label_1.grid(row = 0, column = 0, sticky = W) 
        self.input_1 = Entry(f3)
        self.input_1.grid(row = 0, column = 1)

        self.label_2 = Label(f3, text= names[1])
        self.label_2.grid(row = 1, column = 0, sticky = W)
        self.input_2 = Entry(f3)
        self.input_2.grid(row = 1, column = 1)

        # 버튼을 그려주는 부분
        f4 = Frame(frame, width = 100, height = 40)
        f4.grid(row = 1, column = 0)
        

        self.info_button = Button(f4, text="Make", command = self.MakeFile)
        self.info_button.grid(row = 0, column = 0)
        self.info_button = Button(f4, text="Info", command = self.ShowInfo)
        self.info_button.grid(row = 0, column = 1)

    def ShowInfo(self):
        tkMessageBox.showinfo("Information","http://chobocho.com\nVersion 0.2")

    def MakeFile(self):
        self.value1 = self.input_1.get()
        self.value2 = self.input_2.get() 
        
        table[ names[0] ] = self.value1
        table[ names[1] ] = self.value2
        
        self.data = text_data % table

        target = file(self.target_file_name, 'w')
        target.write(self.data)
        target.close()

               
#----------------------------------------------------------
# main
if __name__ == "__main__":      
    root = Tk()
    app = App(root)
    root.mainloop()

'Coding > Python 삽질기' 카테고리의 다른 글

[Python] Undo / Redo 구현하기  (0) 2011.06.16
http://www.pythonchallenge.com...Level6  (0) 2010.12.13
http://www.pythonchallenge.com...Level5  (0) 2010.12.13
Posted by chobocho
Coding/Python 삽질기2010. 12. 13. 01:29

http://www.pythonchallenge.com...Level6


 

import re
import zipfile


def main():

    target = zipfile.ZipFile("channel.zip", 'r')
       
    number = "90052"
    filename = number + ".txt"
    comment = ""

    while 1:   
        print filename
        data = target.read(filename)
        data_ = re.findall("nothing is ([0-9]+)", data)
        if data_:
            comment += target.getinfo(filename).comment
            filename = "".join(data_) + ".txt"
        else:
            break
       
        print comment
         
if __name__ == "__main__":
    main()


'Coding > Python 삽질기' 카테고리의 다른 글

간단한 반복 작업 매크로  (0) 2011.01.12
http://www.pythonchallenge.com...Level5  (0) 2010.12.13
http://www.pythonchallenge.com...Level4  (0) 2010.12.13
Posted by chobocho
Coding/Python 삽질기2010. 12. 13. 01:00

http://www.pythonchallenge.com...Level5


 

import pickle

def main():
    fp = open("banner.p", 'rb')
    data = pickle.load(fp)
   
    for li in data:
        line = ""
        for ch, count in li:
            line += ch*count
        print line
   
       
if __name__ == "__main__":
    main()


'Coding > Python 삽질기' 카테고리의 다른 글

http://www.pythonchallenge.com...Level6  (0) 2010.12.13
http://www.pythonchallenge.com...Level4  (0) 2010.12.13
http://www.pythonchallenge.com...Level3  (0) 2010.12.12
Posted by chobocho
Coding/Python 삽질기2010. 12. 13. 00:37

http://www.pythonchallenge.com...Level4


 

import urllib
import re


def main():

    url = "http://www.pythonchallenge.com/pc/def/linkedlist.php?nothing="
   
    url_to = url + "12345"
    #url_to = url + "46059" # After get new messages.
   
    while 1:
        source = urllib.urlopen(url_to)
        data = source.read()
        number = re.findall("nothing is ([0-9]+)", data)
        if number:
           url_to = url + "".join(number)
           print url_to
        else:
           break
       
    print data
   
   
if __name__ == "__main__":
    main()

'Coding > Python 삽질기' 카테고리의 다른 글

http://www.pythonchallenge.com...Level5  (0) 2010.12.13
http://www.pythonchallenge.com...Level3  (0) 2010.12.12
http://www.pythonchallenge.com...Level2  (0) 2010.12.06
Posted by chobocho
Coding/Python 삽질기2010. 12. 12. 23:11

http://www.pythonchallenge.com...Level3


 

import re

data_ = """_abaAAAbCCC"""

def main():
    p = re.compile ('[a-z]{1}[A-Z]{3}[a-z]{1}[A-Z]{3}[a-z]{1}')
    m = p.findall(data_)
   
    if m:
        print m
        for idx in m:
            print idx[4],
   
   
if __name__ == "__main__":
    main()

'Coding > Python 삽질기' 카테고리의 다른 글

http://www.pythonchallenge.com...Level4  (0) 2010.12.13
http://www.pythonchallenge.com...Level2  (0) 2010.12.06
[Python] 파일 zip으로 압축하기  (0) 2010.10.25
Posted by chobocho
Coding/Python 삽질기2010. 12. 6. 23:34

http://www.pythonchallenge.com...Level2

data='''
find at source code...
'''

def main():
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    result = filter(lambda x : x in alphabet, data)
   
    print result
   
if __name__ == "__main__":
    main()

'Coding > Python 삽질기' 카테고리의 다른 글

http://www.pythonchallenge.com...Level3  (0) 2010.12.12
[Python] 파일 zip으로 압축하기  (0) 2010.10.25
1000!  (0) 2010.07.14
Posted by chobocho
Coding/Python 삽질기2010. 10. 25. 00:25

[Python] 파일 zip으로 압축하기

#-*- coding: cp949 -*-
# 파일 명을 받아서 압축해 주는 스크립트

import os
import sys
import glob
import zipfile


def main(files):
    file_number = len(files)
    target_file = files[1];
        
    target = zipfile.ZipFile(target_file, 'w')
 
    for idx in range (2, file_number):
        all_flist = glob.glob (files[idx])
        for f in all_flist:
            if os.path.isdir(f):
                pass
            target.write(f)
   
    target.close()
  

#-------------------------------------------------------------------------------
# main
if __name__ == "__main__": 
    if len(sys.argv) < 3:
        print "Usage : pyzip source1 [source2]*"
    else:
        main(sys.argv)


'Coding > Python 삽질기' 카테고리의 다른 글

http://www.pythonchallenge.com...Level2  (0) 2010.12.06
1000!  (0) 2010.07.14
Self number ... 2  (0) 2010.07.13
Posted by chobocho

티스토리툴바