Cod sursa(job #3139463)

Utilizator Luca07Nicolae Luca Luca07 Data 28 iunie 2023 13:40:53
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include<string>
#include<vector>
using namespace std;

vector<int> res;
int length = 0;

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

void solve(string s1, string s2) {
    int l1 = s1.length(), l2 = s2.length();
    vector<int> lps = vector<int>(l2, 0);
    int i, j, prevLps = 0;

    i = 1;
    while (i < l2) {
        if (s2[prevLps] == s2[i]) {
            lps[i] = prevLps + 1;
            prevLps++;
            i++;
        }
        else if (prevLps == 0) {
            lps[i] = 0;
            i++;
        }
        else {
            prevLps = lps[prevLps - 1];
        }
    }

    i = 0;
    j = 0;
    while (i < l1) {
        if (s1[i] == s2[j]) {
            i++;
            j++;
        }
        else if (j == 0) {
            i++;
        }
        else {
            j = lps[j - 1];
        }

        if (j == l2) {
            j--;
            i -= l2;
            length++;
            res.push_back(i);
            if (length == 1000)
                return;
            i++;
        }
    }
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;

    solve(s2, s1);
    
    cout << length << "\n";
    for (auto nr : res) {
        cout << nr << " ";
    }

    return 0;
}