Cod sursa(job #2241801)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 17 septembrie 2018 02:23:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <list>
#include <fstream>
#include <string.h>
using namespace std;
//list <int>li;
//list<int>::iterator in;
char A[2000001], B[2000001];
int v[1111], c,T[2000001], nr,jmenesimtitdarlegit[300];
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int i=1,a, b, k = 0;
    f.getline(A,2000001);
    a = strlen(A);
    f.getline(B,2000001);
   // b = strlen(B);
    while(A[i])
    {
    //jmenesimtitdarlegit[A[i]]++;
        if(A[i] == A[k])
        {
            k++;
            T[i] = k;
            i++;
        }
        else
        {
            k = T[k-1];
            if(k == 0&&A[0]!=A[i])i++;
        }
    }
    i=0;
    k=0;

    while(B[i])
    {
        if(B[i] == A[k])
        {
            k++;
            i++;
            if(k == a)
            {
                if(nr<1002)
                    v[nr] = i-a;
                nr++;
                k = T[k-1];
            }
        }
        else
        {
            if(k)
            k=T[k-1];
            else
            if(B[i]!=A[0])i++;
        }

    }
    g<<nr<<"\n";
    if(nr>1000)
        nr=1000;
    for(i = 0; i<nr; i++)
        g<<v[i]<<" ";

    return 0;
}