Cod sursa(job #2241675)

Utilizator catalin9898Bajenaru Catalin catalin9898 Data 16 septembrie 2018 18:02:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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[2111111], nr;
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    int i=0, 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;
        }
        else k = 0;
    }
    i=0;
    k=0;
    while(B[i])
    {
         if(i == 262081)
        {
          //  nr--;
          j++;
        }
        if(B[i] == A[k])
        {
            k++;
            i++;
            if(k == a)
                {
                    v[nr] = i-a;
                    nr++;
                    k = T[k - 1];
                }
        }
        else
        {
            //k = T[k];
           k=T[k-1];
           if(!k&&B[i]!=A[k])i++;

        }

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

    return 0;
}