Cod sursa(job #2723105)

Utilizator Rares09Rares I Rares09 Data 13 martie 2021 15:57:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

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

int v[2000005];
vector <int> sol;
string pattern, s;

void prefixsufix()
{
    int n = pattern.length(), i = 0;
    v[0] = 0;

    for(int j = 1; j < n; ++j)
    {
        while(i != 0 && pattern[i] != pattern[j])
            i = v[i - 1];

        if(pattern[i] == pattern[j])
            ++i;

        v[j] = i;
    }
}

int main()
{
    getline(cin, pattern);
    getline(cin, s);
    prefixsufix();
    int n = s.length(), m = pattern.length(), j = 0;

    for(int i = 0; i < n; ++i)
    {
        while(j != 0 && (j >= m || pattern[j] != s[i]))
            j = v[j - 1];

        if(pattern[j] == s[i])
            ++j;

        if(j == m)
        {
            sol.push_back(i - m + 1);
        }
    }

    cout << sol.size() << '\n';

    for(auto it = sol.begin(); it != sol.end(); ++it)
    {
        cout << *it << ' ';
    }

    return 0;
}