Pagini recente » Cod sursa (job #1320511) | Cod sursa (job #732239) | Cod sursa (job #826696) | Cod sursa (job #570657) | Cod sursa (job #2800701)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
vector <int> v;
int lps[2000005];
int main()
{
fin >> a >> b;
a = " " + a;
b = " " + b;
lps[1] = 0;
for (int i = 2; i < a.size(); i++)
{
char currLetter = a[i];
int currIndex = lps[i - 1];
while (currLetter != a[currIndex + 1] && currIndex != 0)
{
currIndex = lps[currIndex];
}
int result = currIndex;
if (currLetter == a[currIndex + 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)
{
v.push_back(i - a.size() + 1);
}
}
// ABA
// CABBCABABAB
//0 1 2 0 0 1 2 3 2 3 2
fout << v.size() << '\n';
for (int i : v)
{
fout << i << ' ';
}
fout << '\n';
//ABACDABAB
//00100123
}