Pagini recente » Cod sursa (job #801163) | Cod sursa (job #988195) | Cod sursa (job #1091096) | Cod sursa (job #2386794) | Cod sursa (job #2800704)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
vector <int> solutions;
int lps[2000005];
int main()
{
fin >> a >> b;
a = " " + a;
b = " " + b;
lps[1] = 0;
// build lps
for (int i = 2; i < a.size(); i++)
{
char currLetter = a[i];
// the current lps value
int currIndex = lps[i - 1];
while (currLetter != a[currIndex + 1] && currIndex != 0)
{
// get the prefix of the prefix of the prefix of the.... yes.
currIndex = lps[currIndex];
}
int result = currIndex;
if (currLetter == a[currIndex + 1])
{
// if letters match we increase the lps value by 1
result++;
}
lps[i] = result;
}
int currIndex = 0;
for (int i = 1; i < b.size(); i++)
{
char currLetter = b[i];
while (currLetter != a[currIndex + 1] && currIndex != 0)
{
currIndex = lps[currIndex];
}
// currIndex is the length of the pattern
if (currLetter == a[currIndex + 1])
{
currIndex++;
}
if (currIndex == a.size() - 1) // size - 1 beacause we did a = " " + a
{
solutions.push_back(i - a.size() + 1);
}
}
// output to file
fout << solutions.size() << '\n';
for (int i = 0; i < 1000 && i < solutions.size(); i++)
{
fout << solutions[i] << ' ';
}
fout << '\n';
}