Cod sursa(job #2716498)

Utilizator seburebu111Mustata Dumtru Sebastian seburebu111 Data 5 martie 2021 11:45:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int N = 2000002;

char a[N], b[N];
int pi[N];
int rasp[N];

int main()
{
    in>>(1+a)>>(1+b);
    int lung = 0;
    int m=strlen(1+a);
    int n=strlen(1+b);
    pi[1] = 0;
    for(int i=2; i<=m; i++)
    {
        while(lung > 0 && a[i]!=a[lung+1])
        {
            lung = pi[lung];
        }
        if(a[i]==a[lung+1])
        {
            lung++;
        }
        pi[i]=lung;
    }

    /*
    for(int i=1; i<=m; i++)
        cout<<pi[i]<<' ';
    */

    lung =0;
    int k=0;
    for(int i=1; i<=n; i++)
    {
        while(lung>0 && b[i]!=a[lung+1])
        {
            lung=pi[lung];
        }
        if(b[i]==a[lung+1])
        {
            lung++;
        }
        if(lung==m)
            rasp[++k]=i-lung;
    }
    out<<k<<'\n';
    for(int i=1; i<=k; i++)
        out<<rasp[i]<<' ';
    return 0;
}