OJ Board

I'm sure I already read something about min cost matching on this forum, try searching

If you don't get any help here, you can try the usaco forum

This is not Boyer-Moore, this is Quick search algorithm
http://www-igm.univ-mlv.fr/~lecroq/stri ... CTION00190
Notice the O(n*m) running time

why don't you post your code?

KMP is O(N+M), which is worst case optimal. Boyer-Moore variants also have O(N+M) worst case, but their best case can be down to O(M+N/M), which is much better. If you are searching for more then one pattern, use Aho-Corasick. Is there a particular problem that you are trying to solve?

This is something like usaco fence4 problem. general idea of my solution was to keep line segments that are visible so far, to add one new at a time, checking those you examined so far: if part of a line segment is not visible, we can break it in two ( or less ) visible parts and continue checking ...

I solved Cave Cows 2 like this: divide the segments into groups of 50, and preprocess the min of every group. Example querry: what is min from 117 to 873?
Compute "manually" min from 117 to 150, then you now mins from 150-200, 200-250, ... , 800-850, then manually from 850-873 again. Maximal time to ...

I used similar method, only I used binary search to limit the maximal path length and then maximal flow to see if all the cows can get to shelter. I had a nasty bug so actually won no points on it, but later I had 10 test cases on time, and the rest was TL.
In fact, no one solved this problem ...

search() calls itself several thousand times and you run out off stack, I haven't studied why. pozdrav

Try this, it is O(N*M)

#include <cstdio>
#include <vector>
using namespace std;

int main() {
int N,M,cnt=0;
scanf ("%d %d",&N,&M);
vector <int> weight(N),amount(N), V(M+1), R(M+1);
for (int i=0;i<N;i++)
scanf ("%d %d",&weight[i],&amount[i]);

V[0]=1;
for (int i=0;i<N;i++) {
int w=weight ...

to start off, try rabin karp string matching algorithm

i got accepted without the additional newlines, like D-DY first output.

I used Grahm's scan and got WA. With almost identical code I passed convex hull problem on USACO. I've checked test cases posted above, works fine. Anyone has an idea about where the error might be? Any new test data?

// FINDING THE COMPLEX HULL USING GRAHM'S SCAN
#include <cstdio>
#include ...

Problem: given a text determine lexicographically maxiaml suffix of a string in O(n).

For example:
cacbca has the max suffix cbca.

I read that this can be done with technique similar to one used in KMP, using the maximal suffix and at the same time a prefix of a word, but I don't know how to ...

you don't need any pruning at all, test cases are that simple.