Cod sursa(job #2416039)

Utilizator GoogalAbabei Daniel Googal Data 26 aprilie 2019 20:15:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

const int NMAX = 2 * (2 * 1e6 + 1e2);

int nsol;
int pref[1 + NMAX];

string s1;
string s2;

vector < int > res;

void precompute(string s)
{
    int i = 0;
    int j = 1;

    pref[0] = 0;
    while(j < s.size())
    {
        if(s[i] == s[j])
        {
            pref[j] = i + 1;
            i++;
            j++;
        }
        else
        {
            if(i > 0)
                i = pref[i - 1];
            else
            {
                pref[j] = 0;
                j++;
            }
        }
    }
}

int main()
{
    in >> s1 >> s2;

    precompute(s1 + '*' + s2);

    for(int i = s1.size(); i < s1.size() + s2.size() + 1; i++)
    {
        if(pref[i] == s1.size())
        {
            nsol++;

            if(nsol <= 1000)
            {
                res.push_back(i - 2 * s1.size());
            }
        }
    }

    out << nsol << '\n';

    for(int i = 0; i < res.size(); i++)
        out << res[i] << ' ';

    out << '\n';

    in.close();
    out.close();

    return 0;
}