Cod sursa(job #3039736)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 28 martie 2023 20:15:38
Problema Potrivirea sirurilor Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <vector>
using namespace std;

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

const int MAX = 2e6 + 1;

string a , b;

int cat[MAX] , n , m;

vector <int> poz;

int main()
{

    cin >> a >> b;

    n = a.size();
    m = b.size();

    int i;

    int contor = 0;

    for(i = 1 ; i < n ; i++){

        if( a[i] == a[0] ){

            contor++;

            break;
        }
    }

    cat[i++] = 1;

    for( ; i < n ; i++){

        if( a[i] == a[contor] ){

            cat[i] = cat[i-1] + 1;

            contor++;

        }else{

            contor = 0;

            if( a[i] == a[contor] ){

                cat[i] = 1;

                contor++;
            }
        }
    }

    for(int i = 0 ; i < m ;){

        if(a[0] != b[i]){

            i++;
            continue;
        }

        int k = 0 , ogi = i;

        while(k < n && i < m && a[k] == b[i]){

            k++;
            i++;
        }

        if(k == n) poz.push_back(ogi);

        k--;

        i = ogi + k - cat[k];
    }

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

    for(auto it : poz){

        cout << it << ' ';
    }

    return 0;
}