Cod sursa(job #3329430)

Utilizator SoniaMaria2008Sonia Maria Manjina SoniaMaria2008 Data 13 decembrie 2025 10:34:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    char A[2000000], B[2000000];
    f>>A>>B;
    int lenA=strlen(A);
    vector<int> p(lenA);
    int l=0;
    for(int i=1; i<lenA; i++)
    {
        if(A[i]==A[l])
        {
            l++;
            p[i]=l;
        }
        else
        {
            while(A[i]!=A[l] && l>0)
            {
                l=p[l-1];
            }
            if(A[i]==A[l])
            {
                l++;
            }
           p[i]=l;
        }
    }
    int num=0;
    l=0;
    vector<int> poz;
    int lenB=strlen(B);
    for(int i=0; i<lenB; i++)
    {
        while(A[l]!=B[i] && l>0)
        {
            l=p[l-1];
        }
        if(A[l]==B[i])
        {
            l++;
        }
        if(lenA==l)
        {
            num++;
            if(poz.size()<1000)
            {
             poz.push_back(i-lenA+1);
            }
            l=p[l-1];
        }
    }
    g<<num<<endl;
    for(int i=0; i<poz.size(); i++)
    {
        g<<poz[i]<<" ";
    }
    

    return 0;
}