Pagini recente » Cod sursa (job #2628239) | Cod sursa (job #1239008) | Cod sursa (job #2142846) | Cod sursa (job #1819546) | Cod sursa (job #3204790)
//Algoritmul lui Z - Complexitate O(n)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
string pattern,text;
long long sol;
int Z[4000003];
vector <int> V;
void construct_Z(string S,int Z[]);
// prints all occurrences of pattern in text using Z algo
void solve(string text, string pattern)
{
// Create concatenated string "P$T"
string concatenat='0'+pattern+text;
int l=concatenat.length()-1;
// Construct Z array
construct_Z(concatenat,Z);
// now looping through Z array for matching condition
for(int i=pattern.size()+1;i<=l;i++)
{
// if Z[i] (matched region) is equal to pattern
// length we got the pattern
if(Z[i]>=pattern.length())
{
sol++;
if(sol<=1000)
V.push_back(i-pattern.length()-1);
}
}
fout<<sol<<"\n";
for(auto j:V)
fout<<j<<" ";
}
// Fills Z array for given string str[]
///Z[i] reprezinta cea mai lunga lungime a prefixului care incepe din i si apartine pattern-ului
void construct_Z(string S,int Z[])
{
int l=S.length()-1;
int st,dr,k;
// [L,R] make a window which matches with prefix of s
st=dr=1;
for(int i=2;i<=l;i++)
{
// if i>R nothing matches so we will calculate.
// Z[i] using naive way.
if(i>dr)
{
st=i;
dr=i;
// R-L = 0 in starting, so it will start
// checking from 0'th index. For example,
// for "ababab" and i = 1, the value of R
// remains 0 and Z[i] becomes 0. For string
// "aaaaaa" and i = 1, Z[i] and R become 5
while(dr<=l&&S[dr-st+1]==S[dr])
dr++;
dr--;
Z[i]=dr-st+1;
}
else
{
// k = i-L so k corresponds to number which
// matches in [L,R] interval.
k=i-st+1;
// if Z[k] is less than remaining interval
// then Z[i] will be equal to Z[k].
// For example, str = "ababab", i = 3, R = 5
// and L = 2
if (Z[k]<dr-i+1)
Z[i]=Z[k];
// For example str = "aaaaaa" and i = 2, R is 5,
// L is 0
else
{
// else start from R and check manually
st=i;
while(dr<=l&&S[dr-st+1]==S[dr])
dr++;
dr--;
Z[i]=dr-st+1;
}
}
}
}
int main()
{
fin>>pattern;
fin>>text;
solve(text,pattern);
return 0;
}