Cod sursa(job #1046566)

Utilizator mikeshadowIon Complot mikeshadow Data 3 decembrie 2013 09:29:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>

#define min(a,b) ((a<b)?a:b)
#define max(a,b) ((a<b)?b:a)
#define abs(a) ((a<0)?-a:a)

#define INF 1000001

using namespace std;


#ifndef TEST
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
#else
ifstream fin ("input.txt");
ofstream fout ("output.txt");
#endif

#define MAXN 2000000

string s,t;

vector<int> sol;

int T[MAXN+1];

void build()
{
    int c = 0;
    T[0] = -1;
    T[1] = 0;
    for (int i=2; i<s.length(); i++)
    {
        if (s[i-1]==s[c])
        {
            c++;
            T[i]=c;
        } else if (c>0)
        {
            c = T[c];
            i--;
        } else T[i]=0;
    }
}

int main()
{
    fin>>s>>t;

    int sl,tl;
    sl = s.length();
    tl = t.length();

    build();

    int c=0,i=0;
    while (i+sl <= tl)
    {
        if (t[i+c]==s[c])
        {
            if (c==sl-1)
            {
                sol.push_back(i);
                i =i+c- T[c];
                if (T[c]>-1)
                c = T[c];
                else c=0;
            }
            else c++;
        } else
        {
            i = i+c -T[c];
            if (T[c]>-1)
                c = T[c];
            else c=0;
        }
    }

    fout<<sol.size();
    fout<<'\n';

    for (int i=0; i<min(sol.size(),1000); i++)
        fout<<sol[i]<<' ';
    return 0;
}