Cod sursa(job #661120)

Utilizator psycho21rAbabab psycho21r Data 13 ianuarie 2012 20:33:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    string s, w;
    vector <int> sol;
    ifstream in("strmatch.in");
    in >> w >> s;
    in.close();
    int i, j, next = 0, nexti, wlen = w.length(), slen = s.length();
    bool before;
    while(next + wlen <= slen)
    {
        before = false;
        j = 0;
        for (i = next; i < wlen + next; ++i)
        {
            if(s[i] == w[0] && i > next && !before)
            {
                nexti = i;
                before = true;
            }
            if(s[i] != w[j++])
            {
                if(!before)
                    next = i + 1;
                else
                    next = nexti;
                break;
            }

            if(j == wlen)
            {
                sol.push_back(i-wlen+1);
                if(!before)
                    next = i + 1;
                else
                    next = nexti;
                break;
            }
        }
        if(sol.size() >= 1000)
            break;
    }

    ofstream out("strmatch.out");
    out << sol.size() << "\n";
    for (int i = 0; i < sol.size(); ++i)
        out << sol[i] << " ";
    out.close();
    return 0;
}