Cod sursa(job #901742)

Utilizator paul.chPaul Chelarescu paul.ch Data 1 martie 2013 11:31:51
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 3.49 kb
//#include <iostream>
#include<fstream>
//#include<math.h>
//#include<string>
//#include<stack>
//#include<windows.h>
//#include<time.h>
//#include<queue>
using namespace std;
long long pos, cnd /*candidates*/, T[2000010],  vector[2000010];
//int ;
//stack <int> ;
string W, S;
//struct e
//{
//}
//queue <e>;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
inline void citire()
{
    getline(fin, W);
    getline(fin, S);
}
int main()
{
    citire();
//algorithm kmp_table:
//    input:
//        an array of characters, W (the word to be analyzed)
//        an array of integers, T (the table to be filled)
//    output:
//        nothing (but during operation, it populates the table)
//
//    define variables:
//        an integer, pos ← 2 (the current position we are computing in T)
//        an integer, cnd ← 0 (the zero-based index in W of the next
//character of the current candidate substring)
//
//    (the first few values are fixed but different from what the algorithm
//might suggest)
//        let T[0] ← -1, T[1] ← 0
//    while pos is less than the length of W, do:
//        (first case: the substring continues)
//        if W[pos - 1] = W[cnd],
//          let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
//
//        (second case: it doesn't, but we can fall back)
//        otherwise, if cnd > 0, let cnd ← T[cnd]
//
//        (third case: we have run out of candidates.  Note cnd = 0)
//        otherwise, let T[pos] ← 0, pos ← pos + 1
    T[0] = -1;
    T[1] = 0;
    pos = 2;
    while(pos <= W.length())
    {
        if(W[pos - 1] == W[cnd])
        {
            ++cnd;
            T[pos] = cnd;
            ++pos;
        }
        else
        {
            if(cnd > 0)
            {
                cnd = T[cnd];
            }
            else
            {
                T[pos] = 0;
                ++pos;
            }
        }
    }
//algorithm kmp_search:
//    input:
//        an array of characters, S (the text to be searched)
//        an array of characters, W (the word sought)
//    output:
//        an integer (the zero-based position in S at which W is found)
//
//    define variables:
//        an integer, m ← 0 (the beginning of the current match in S)
//        an integer, i ← 0 (the position of the current character in W)
//        an array of integers, T (the table, computed elsewhere)
//
//    while m+i is less than the length of S, do:
//        if W[i] = S[m + i],
//            if i equals the (length of W)-1,
//                return m
//            let i ← i + 1
//        otherwise,
//            let m ← m + i - T[i],
//            if T[i] is greater than -1,
//                let i ← T[i]
//            else
//                let i ← 0
//
//    (if we reach here, we have searched all of S unsuccessfully)
//    return the length of S
    long long m = 0, i = 0,contor = 0;
    while(m + i <= S.length())
    {
        if(W[i] == S[m + i])
        {
            if(i == W.length() - 1)
            {
                vector[contor++] = m;
            }
            ++i;
        }
        else
        {
            m += i - T[i];
            if(T[i] > - 1)
            {
                i = T[i];
            }
            else
            {
                i = 0;
            }
        }
    }
    fout << contor << '\n';
    for(long long u = 0; u < contor; ++u)
    {
        fout << vector[u] << ' ';
    }
    return 0;
}