Pagini recente » Cod sursa (job #749387) | Cod sursa (job #503941) | Cod sursa (job #2672208) | Cod sursa (job #2399184) | Cod sursa (job #901742)
Cod sursa(job #901742)
//#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;
}