Cod sursa(job #2063215)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 11 noiembrie 2017 10:14:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
char sir[2000005],a[2000005],ap[2000005];
vector <int> sol;
void constructV()
{
    int l=strlen(a),delta=0,ok;
    for(int i=0; i<l; i++)
    {
        ok=0;
        while(a[delta]==a[i]&&delta!=i)
        {
            ap[i]=delta+1;
            delta++;
            i++;
            ok=1;
        }
        if(ok)
            i--;
        delta=ap[delta-1];
    }
}
void cautare()
{
    int l1=strlen(sir);
    int l2=strlen(a);
    int delta=0,ok;
    for(int i=0; i<l1; i++)
    {
        ok=0;
        while(delta<l2&&i<l1&&sir[i]==a[delta])
        {
            ok=1;
            i++;
            delta++;
        }
        if(delta==l2&&sol.size()<1000)
            sol.push_back(i-l2);
        if(ok)
            i--;
        delta=ap[delta-1];
    }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",&a);
    scanf("%s\n",&sir);
    constructV();
    //for(int i=0;i<strlen(a);i++)
        //printf("%d ",ap[i]);
    cautare();
    printf("%d\n",sol.size());
    for(int i=0;i<sol.size();i++)
        printf("%d ",sol[i]);


    return 0;
}