Cod sursa(job #2653538)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 28 septembrie 2020 14:25:18
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>

using namespace std;

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

string s;
string a, b;

unsigned int p[4000000 + 7];

int main()
{
    in >> a >> b; s = '*' + a + '*' + b;
    unsigned int k = 0;
    for(unsigned int i = 2; i < s.size(); i++)
    {
        while(k > 0 && s[k+1] != s[i])
            k = p[k];
        if(s[k+1] == s[i])
            k++;
        p[i] = k;
    }

    int nr_ap = 0;
    for(unsigned int i = 0; i < s.size(); i++)
    {
        //cout << p[i] << endl;

        if(p[i] == a.size())
            nr_ap++;
    }

    out << nr_ap << endl;
    for(unsigned int i = 0; i < s.size(); i++)
    {
        if(p[i] == a.size())
            out << i - 1 - 2*a.size() << " ";
    }
}