Oulipo

Problem's Link

----------------------------------------------------------------------------

Mean:

给你一个模式串P和一个母串S，让你统计P串在S串中出现的次数.

analyse:

一开始想到的就是使用KMP，就用KMP写了，93ms，挺快的.

我又用AC自动机写了一遍，万万没想到竟然超时了.

后来看别人有用字符串hash写的，于是又用字符串hash写了一遍，代码30+行，而且速度也挺快，173ms.

字符串hash确实是一个好东西在字符串hash中又学到了unsigned long long超范围后会自动对2^64取模，省去了手动取模.

Time complexity: O(N+M)

view code

1.字符串hash代码

;
;
;);
;);
;
));
;
}

2.KMP代码

;
);
;;;
;;
}

3.AC自动机(TLE)

;
; ; ;
;
; ; ;
;
;
)
)
;
;
}

--------------------------------------------------------- End.

转载请注明：http://www.cnblogs.com/crazyacking/