Cod sursa(job #1220604)

Utilizator goalexboxerFMI Alexandru Ionascu goalexboxer Data 17 august 2014 20:44:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<vector>
#include<fstream>
#include<string.h>
using namespace std;

#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define MAX 2000002

ifstream f(FIN);
ofstream g(FOUT);

char A[MAX];
char B[MAX];
int table[125]; //bad mismatch table
vector<int> solution;
int count;

void read()
{
    f.getline(A, MAX);
    f.getline(B, MAX);
}

int compare(int index, int length)
{
    for(int i=0;i<length;i++)
    {
        if(A[i] != B[index + i])
            return 1;
    }

    return 0;
}

void solve()
{

    int length = strlen(A);
    int strlength = strlen(B);
    //preprocessing
    //ASCII intervals for numbers and letters
    //48 - 57 , 65-90 , 97 - 122
    for(int i=1; i < length -1; i++)
    {
        table[(int)A[i]] = length - i - 1;
    }
    //the last letter
    if(table[(int)A[length]] == 0)
        table[(int)A[length]] = length;

    //comparation

    int index = 0;
    while(index + length <= strlength)
    {

        if(compare(index, length) == 0)
        {
            count++;
            solution.push_back(index);
            index++;
        }
        else
        {
            if(table[B[index + length - 1]] == 0)
            {
                index += length;
            }
            else
            {
                index += table[B[index + length - 1]];
            }
        }
    }

}

void write()
{
    g << count << endl;
    for(vector<int>::iterator it = solution.begin(); it!=solution.end(); it++)
        g << *it << " ";
}

int main()
{
    read();
    solve();
    write();



    return 0;
}