Cod sursa(job #2241800)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 17 septembrie 2018 02:04:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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[11111], c,T[2111111], nr;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int i=1, j, n, a, b, k = 0;
    f.getline(A,2000001);
    a = strlen(A);
    // f.getline(B,2000);
    f.getline(B,2000001);
    // g<<A<<endl<<B<<endl;
    b = strlen(B);
    while(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;
   // T[0]=-1;
    while(B[i])
    {
        if(i == 1080)
        {
            //  nr--;
            j++;
        }
        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(k==0&&B[i]!=A[0])i++;
           // if(k<0){k=0;i++;}
           // if(B[i]!=A[k])
             //   i++;



        }

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

    return 0;
}