Cod sursa(job #1405159)

Utilizator grayshadeLaurentiu Nicola grayshade Data 28 martie 2015 21:58:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    ifstream fi("strmatch.in");
    ofstream fo("strmatch.out");
    string s;
    string w;
    
    getline(fi, w);
    getline(fi, s);

    int rcount = 0;

    vector<int> rpos;
    vector<int> t(w.size());
    
    t[0] = -1;
    t[1] = 0;

    int pos = 2;
    int cnd = 0;
    while (pos < w.size())
    {
        if (w[pos - 1] == w[cnd])
        {
            cnd = cnd + 1;
            t[pos] = cnd;
            pos = pos + 1;
        }
        else if (cnd > 0)
        {
            cnd = t[cnd];
        }
        else
        {
            t[pos] = 0;
            pos = pos + 1;
        }
    }

    int m = 0;
    int i = 0;
    while (m + i < s.size())
    {
        bool ok = false;
        if (w[i] == s[m + i])
        {
            ok = true;
            if (i == w.size() - 1)
            {
                rpos.emplace_back(m);
                if (rpos.size() == 1000)
                {
                    break;
                }
                ok = false;
                i--;
            }
            i++;
        }

        if (!ok)
        {
            if (t[i] > -1)
            {
                m = m + i - t[i];
                i = t[i];
            }
            else
            {
                i = 0;
                m = m + 1;
            }
        }
    }

    fo << rpos.size() << '\n';
    for (auto p : rpos)
        fo << p << ' ';
}